Complexity Analysis
Loading
Loading
Complexity Analysis
Counting memory, what conventionally does not count, and the trade against time.
By the end of this chapter
Space complexity measures the extra memory an algorithm needs as the input grows. By convention the input itself does not count, and neither does the output — you were given one and are obliged to produce the other.
Concept
Everything you allocate that is neither the input nor the output. A few loop counters are O(1). A hash map holding every element is O(n). A new array the size of the input is O(n), even if you are about to return it — in which case most people call it O(1) auxiliary and say so.
def running_max(nums): best = nums[0] # O(1): one variable for value in nums: best = max(best, value) return best def all_prefix_maxima(nums): result = [] # O(n): grows with the input best = nums[0] for value in nums: best = max(best, value) result.append(best) return resultEvery pending call keeps a frame on the call stack, holding its parameters and local variables. A recursion n levels deep costs O(n) memory even if it allocates nothing.
def sum_to(n): if n == 0: return 0 return n + sum_to(n - 1) # n frames alive at the deepest pointTime and space pull against each other, and the exchange rate is usually very favourable in one direction.
| Approach | Time | Space |
|---|---|---|
| Compare every pair | O(n²) | O(1) |
| Sort, then scan | O(n log n) | O(log n) to O(n) |
| Hash set of what you have seen | O(n) | O(n) |
Quick quiz
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: take the quiz above, and try 1 practice problem.