Space Complexity Explained (With Python Examples)

Space complexity describes how much extra memory an algorithm needs as the input grows. It uses the same Big O notation as time.

We usually count only the auxiliary space: memory the algorithm creates itself, not the input it was given.

O(1) space: a few variables#

def find_max(items):
    best = items[0]          # one variable
    for x in items:
        if x > best:
            best = x
    return best

print(find_max([3, 17, 8, 21, 5]))

21

However long the list is, the function only ever keeps best and x. That is O(1) extra space.

O(n) space: building something as big as the input#

def squares(items):
    result = []
    for x in items:
        result.append(x * x)   # result grows to n items
    return result

print(squares([1, 2, 3, 4]))

[1, 4, 9, 16]

The new list has one entry per input item: O(n) space.

In-place algorithms#

An in-place algorithm changes the input directly instead of building a copy. Reversing a list both ways:

def reversed_copy(items):
    return items[::-1]               # new list: O(n) space

def reverse_in_place(items):
    left, right = 0, len(items) - 1
    while left < right:              # O(1) space: two indexes
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1

data = [1, 2, 3, 4, 5]
print(reversed_copy(data), data)
reverse_in_place(data)
print(data)

[5, 4, 3, 2, 1] [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]

The copy leaves data unchanged but needs n extra slots. The in-place version needs only two indexes, but it modifies the caller's list. Which one is right depends on whether the caller still needs the original.

Recursion uses memory too#

Every recursive call waits on the call stack until the calls below it return. A recursion that goes n levels deep uses O(n) space, even with no lists in sight:

import sys

def depth(n):
    if n == 0:
        return 0
    return 1 + depth(n - 1)

print(depth(500))
print("Python's default recursion limit:", sys.getrecursionlimit())

500
Python's default recursion limit: 1000

Asking for depth(5000) would raise RecursionError, because Python stops the stack at its limit. A loop that does the same counting needs O(1) space. More on this in Recursion.

The time-memory trade-off#

Spending memory often saves time. Answering "how many times does each word appear?" for many queries:

text = "the cat and the hat and the bat"
words = text.split()

# Option 1: no extra memory, O(n) per question
print(words.count("the"))

# Option 2: O(n) memory once, then O(1) per question
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print(counts["the"], counts["and"])

3
3 2

If you ask one question, counting directly is fine. If you ask thousands, building the dictionary once is far faster overall.

Common mistakes#

Practice#

def running_total(items):
    for i in range(1, len(items)):
        items[i] += items[i - 1]

data = [1, 2, 3, 4]
running_total(data)
print(data)

[1, 3, 6, 10]

Key takeaway#

Next: functions that call themselves, in Recursion.