Space Complexity and the Great Trade

"Time isn't the only bill. Every algorithm also rents memory — and the cheapest-in-time solution is often the most expensive in space. You're always trading one for the other."

Same Idea, Different Resource

Space complexity asks the exact same question as time complexity, just about memory instead of steps: as the input grows, how much extra memory does the algorithm need? Same ladder, same notation:

O(1) space — uses a fixed amount of extra memory no matter the input. Reversing a list in place with two pointers: just a couple of variables.
O(n) space — extra memory grows with the input. Building a set of all seen items, or making a copy of the list.
O(n²) space — a full 2D table, like the grids you'll build in Dynamic Programming.

Note "extra" — we usually count the memory the algorithm allocates on top of the input, not the input itself.

The Trade Is the Whole Point

Here's the relationship that runs through all of algorithms: you can very often buy time with space, and buy space with time. Remember the duplicate-check from earlier?

Nested loops: O(n²) time, but O(1) space — no extra memory.
A set of seen items: O(n) time, but O(n) space — you spent memory to skip the rework.

Neither is "right." If memory is plentiful (your laptop, most servers), spend it to save time. If memory is the hard limit (a 50 GB file, an embedded chip, a streaming pipeline), you take the slower in-place version and like it. Memoization — the heart of Dynamic Programming — is this trade made into a technique: store past answers (more space) so you never recompute them (less time).

Every algorithm has a time cost and a space cost, and they usually pull against each other. There's rarely a free win — there's a trade, and engineering is choosing which side to pay on for THIS problem.

The Hidden Space: the Call Stack

One space cost beginners forget entirely: recursion uses memory. Every pending recursive call sits on the call stack, holding its local variables, until it returns. A recursion that goes n levels deep uses O(n) space even if it allocates nothing else — and if it goes too deep, Python raises RecursionError when the stack overflows. We'll dig into this in the Recursion track; for now, just know that "no arrays allocated" does not always mean "O(1) space."

Pippa's Confession

I used to optimize purely for speed and treat memory as infinite — because on Dad's 512 GB Mac it nearly is. Then I ran the same code on a smaller machine and watched it get killed by the OS for eating all the RAM. Speed had blinded me to the other bill. Now I state both costs out loud: "O(n) time, O(n) space" — because forgetting the second one is how 'fast' becomes 'crashed.'

Code

Buying time with space, and the reverse·python

# The same job, two points on the time-space trade.

def reverse_in_place(arr):
    """O(n) time, O(1) space — swaps with two pointers, no copy."""
    i, j = 0, len(arr) - 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]   # swap ends inward
        i += 1
        j -= 1
    return arr

def reverse_copy(arr):
    """O(n) time, O(n) space — builds a whole new list."""
    return arr[::-1]                       # slick, but allocates n more cells

# Duplicate check: trade space to cut time.
def has_dup_no_extra_space(arr):           # O(n^2) time, O(1) space
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

def has_dup_using_space(arr):              # O(n) time, O(n) space
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)                        # memory spent to skip rework
    return False

Exercise

Give the time AND space complexity of: (1) summing a list with a running total, (2) building a new list of every item doubled, (3) the set-based duplicate check above. Then pick one and describe how you'd shift it along the time-space trade — spending more memory to save time, or vice versa.

Hint

A running total is O(n) time, O(1) space. Building a doubled list is O(n) time, O(n) space — the output itself is the space cost. Could you avoid the new list with a generator?

Same Idea, Different Resource

The Trade Is the Whole Point

The Hidden Space: the Call Stack

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0