AI Hints
Home›DSA in Python Tutorial›Space and Time
DSA in Python · Lesson 10 of 132

Space Complexity

How much memory?.

⏱ 2 min read▶ Video at 10:18🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Space Complexity
From the video: Space Complexity
  • 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.

space.pypython
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")
Output
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.

More memoryoften means faster
A set of seen itemsO(n) space, O(n) time
Cachingremember answers
Small devicesmemory matters

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
Next up: Timing Real Code — timeit and perf_counter