Space Complexity
How much memory?.
Speed isn't the only cost. Algorithms also use memory. Space complexity uses the same Big O labels, to describe how much extra memory an algorithm needs as the input grows.

- Memory is a cost too
- Same Big O labels
- Extra memory as input grows
O(1) space and O(n) space
Both functions find the total of a list. The first keeps one running total, however long the list is. That's O of one extra space. The second builds a whole new list of running totals first, which grows with the input. That's O of N space. Run it. Same answer, very different memory.
import sys
def total_small(nums):
t = 0
for n in nums:
t += n
return t
def total_big(nums):
running = []
for n in nums:
running.append((running[-1] if running else 0) + n)
return running[-1]
nums = list(range(100_000))
print(total_small(nums), total_big(nums))
print("extra list size:", sys.getsizeof(list(range(100_000))), "bytes")4999950000 4999950000 extra list size: 800056 bytes
Trading space for time
Often you can trade memory for speed. The set in our duplicate check used O of N extra memory, but turned O of N squared time into O of N. Caching saved answers is the same idea. Usually memory is cheap and time is precious, but not always, like on a small device.
Summary
Space complexity measures extra memory, using Big O. You can often trade memory for speed. Next, how to time real code properly.
Key takeaways- Extra memory in Big O
- O(1) vs O(n) space
- Trade space for time