Trade-Offs Between Time and Space

Here’s a function that accepts an array and returns whether it contains any duplicate values (you may recognize this function from Chapter 4, :

	def has_duplicate_value(array):
	for i in range(len(array)):
	for j in range(len(array)):
	if (i != j) and (array[i] == array[j]):
	return True

	return False

This algorithm uses nested loops and has a time complexity of O(N²). We’ll call this implementation Version #1.

Here’s a second implementation, Version #2, that employs a hash table and just a single loop:

	def has_duplicate_value(array):
	existing_values = {}

	for value in array:
	if value not in existing_values:
	existing_values[value] = True
	else:
	return True

	return False

Version #2 starts out with an empty hash table called existing_values. We then iterate over each item from the array, and as we encounter each new item, we store it as a key in the existing_values hash table. (We set the value arbitrarily to True.) If, however, we encounter an item that’s already a key in the hash table, we return True, as it means we found a duplicate value.

Now, which of these two algorithms is more efficient? Well, it all depends on whether you consider time or space. As far as time is concerned, Version #2 is much more efficient, as it’s only O(N), compared with Version #1’s O(N²).

However, when it comes to space, Version #1 is actually more efficient than Version #2. Version #2 consumes up to O(N) space, as it creates a hash table that may end up containing all N values from the array passed to the function. Version #1, however, doesn’t consume any additional memory beyond the original array, and therefore has a space complexity of O(1).

Let’s look at the complete contrast between the two versions of has_duplicate_value:

Version	Time Complexity	Space Complexity
Version #1	O(N²)	O(1)
Version #2	O(N)	O(N)

We can see that Version #1 more efficient when it comes to memory, but Version #2 is faster in terms of raw speed. So how do we decide which algorithm to choose?

The answer, of course, is that it depends on the situation. If we need our application to be blazing fast and we have enough memory to handle it, then Version #2 might be preferable. If, on the other hand, we’re dealing with a hardware/data combination where we need to consume memory sparingly and speed isn’t our biggest need, then Version #1 might be the right choice. Like all technology decisions, when there are trade-offs, we need to look at the big picture.

Let’s look at a third version of this same function and see where it falls compared to the first two versions:

	def has_duplicate_value(array):
	array.sort()

	for i in range(len(array) - 1):
	if array[i] == array[i + 1]:
	return True

	return False

This implementation, which we’ll call Version #3, begins by sorting the array. It then iterates over each value within the array and checks to see whether it’s the same as the next value. If it is, we’ve found a duplicate value. However, if we get to the end of the array and there are no two consecutive values that are the same, we know that the array contains no duplicates.

Let’s analyze the time and space efficiency of Version #3.

In terms of time complexity, this algorithm is O(N log N). We can assume that Python’s sorting algorithm is one that takes O(N log N), as the fastest known sorting algorithms are known to do. The additional N steps of iterating over the array are trivial beside the sorting steps, so O(N log N) is the grand total when it comes to speed.

Space is a slightly more complex matter, as various sorting algorithms consume varying amounts of memory. Some of the earliest algorithms we’ve encountered in the book, like Bubble Sort and Selection Sort, consume no extra space because all the sorting happens in place. Interestingly, though, the faster sorts do take up some space for reasons you’ll see shortly. Most implementations of Quicksort actually take up O(log N) space.

So let’s see where Version #3 lands in comparison with the previous two versions:

Version	Time Complexity	Space Complexity
Version #1	O(N²)	O(1)
Version #2	O(N)	O(N)
Version #3	O(N log N)	O(log N)

It turns out Version #3 strikes an interesting balance between time and space. In terms of time, Version #3 is faster than Version #1 but slower than Version #2. When it comes to space, it’s more efficient than Version #2 but less efficient than Version #1.

So when may we want to use Version #3? Well, if we’re concerned about both time and space, this might be our fix.

Ultimately, in each given situation, we need to know what our minimum acceptable speeds and bounds of memory are. Once we understand our constraints, we can then pick and choose from various algorithms so that we can eke out acceptable efficiency for our speed and memory needs.

Up until this point, you’ve seen how our algorithms can consume extra space when they create additional pieces of data, such as new arrays or hash tables. However, it’s possible for an algorithm to consume space even if it’s not doing any of those things. And this can come to bite us if we’re not expecting it.