Space Complexity

Space complexity measures how much extra memory an algorithm needs as its input grows, expressed as a function of the input size n using Big-O notation. It matters just as much as time complexity: a fast algorithm that runs out of memory is just as unusable as a slow one, and understanding space complexity is what lets you choose between an approach that recomputes values on the fly versus one that stores results for later reuse. In interviews and in real production code, you’re often asked not just how fast is this? but how much extra memory does this use? — and the two questions frequently trade off against each other.

Overview: How Space Complexity Works

The total memory an algorithm touches has two parts: the space needed to hold the input itself, and the auxiliary space — the extra memory the algorithm allocates while it runs, on top of the input. By convention, when someone says an algorithm’s “space complexity” is O(n) or O(1), they almost always mean the auxiliary space, since the input is a given and isn’t something the algorithm chose to allocate. This lesson focuses on auxiliary space unless stated otherwise.

Auxiliary space comes from several sources: local variables, new data structures you build (lists, dicts, sets), and — easy to forget — the call stack used by recursion. Every time a function calls another function (or itself), Python pushes a new stack frame holding that call’s local variables and where to resume afterward. That frame stays alive, consuming memory, until the call it made returns. A recursive function that calls itself n times before hitting a base case therefore needs O(n) stack frames alive at once, even if it never builds an explicit list or dict.

Consider summing a list of numbers. An iterative version keeps one running total in a single variable, so no matter how long the list is, it only ever needs a constant amount of extra memory — O(1) auxiliary space. A naive recursive version that adds the first element to the sum of the rest needs a stack frame for every element before any addition actually happens, giving O(n) auxiliary space. Same result, same time complexity, very different memory profile.

The same Big-O simplification rules that apply to time apply to space: drop constants and lower-order terms. Allocating three separate arrays of size n is still O(n), not O(3n). A fixed handful of variables — no matter how many, as long as the count doesn’t grow with n — is O(1), not “O(5)” or similar.

Common Space Complexity Classes

The table below summarizes the space complexities you’ll see most often, and where they typically come from.

Complexity What grows Typical example
O(1) A fixed number of variables, regardless of input size Iterative find_max, swapping two variables, two-pointer scans
O(log n) Call stack depth when a recursive algorithm halves its input on each call Recursive binary search’s call stack
O(n) A new structure sized proportionally to the input, or a single-branch recursive call stack Copying a list, a memoization dict, recursive factorial
O(n log n) Linear auxiliary storage combined with logarithmic recursion depth Merge sort’s temporary arrays plus its recursion tree (the O(n) term dominates)
O(n^2) A 2D table sized by the input, or repeated copying inside a loop or recursion Dynamic programming grids, adjacency matrices, careless list slicing inside recursion

Space and time are analyzed separately, but they’re often linked by a deliberate choice: memoization spends extra space (usually O(n) for a cache) to avoid recomputing the same subproblem, turning an exponential-time recursive Fibonacci into a linear-time one. That’s a time-space tradeoff — you’re paying memory to buy speed, and recognizing when that trade is worth it is a core DSA skill.

Examples

Example 1: O(1) auxiliary space

Finding the maximum value in a list only ever needs one variable to track the best value seen so far — the amount of extra memory doesn’t change whether the list has 5 elements or 5 million.

def find_max(numbers: list[int]) -> int:
    current_max = numbers[0]
    for number in numbers[1:]:
        if number > current_max:
            current_max = number
    return current_max


values = [3, 7, 2, 9, 4, 1]
result = find_max(values)
print(result)

Output:

9

Tracing through: current_max starts at 3. Comparing against 7, 2, 9, 4, 1 in turn, it updates to 7, stays at 7, updates to 9, and stays at 9 for the rest. Only that single variable is ever allocated beyond the input list itself, so this is O(1) auxiliary space and O(n) time, since it must look at every element once.

Example 2: O(n) new copy vs. O(1) in-place

Doubling every value in a list can be done by building a brand-new list (extra memory proportional to the input) or by mutating the original list index by index (no extra memory beyond a loop counter).

def double_new_list(numbers: list[int]) -> list[int]:
    doubled = []
    for number in numbers:
        doubled.append(number * 2)
    return doubled


def double_in_place(numbers: list[int]) -> None:
    for index in range(len(numbers)):
        numbers[index] *= 2


original = [1, 2, 3, 4]
new_list = double_new_list(original)
print("original:", original)
print("new_list:", new_list)

double_in_place(original)
print("after in-place doubling:", original)

Output:

original: [1, 2, 3, 4]
new_list: [2, 4, 6, 8]
after in-place doubling: [2, 4, 6, 8]

double_new_list allocates a fresh list of size n, so original is unchanged and printed as [1, 2, 3, 4] while new_list holds the doubled values — that’s O(n) auxiliary space. double_in_place overwrites each element by index using only a loop counter, so original becomes [2, 4, 6, 8] with O(1) auxiliary space — but note it destroys the original values, which is a real tradeoff: less memory, but the caller’s data is mutated.

Example 3: O(n) call stack vs. O(1) iteration

Recursive and iterative factorial compute the same answer, but the recursive version needs a stack frame per pending multiplication.

def factorial_recursive(n: int) -> int:
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)


def factorial_iterative(n: int) -> int:
    result = 1
    for value in range(2, n + 1):
        result *= value
    return result


print(factorial_recursive(5))
print(factorial_iterative(5))

Output:

120
120

Both print 120 (5! = 120), but factorial_recursive(5) needs 6 stack frames alive simultaneously (for n = 5, 4, 3, 2, 1, 0) before any multiplication happens, so it uses O(n) auxiliary space. factorial_iterative reuses one result variable across a loop, using O(1) auxiliary space. Both are O(n) time, since both do n multiplications — the difference is purely in memory.

How It Works Step by Step

To see exactly where the recursive call stack’s memory comes from, trace factorial_recursive(4) frame by frame. Each call must wait for the one below it to return before it can multiply and return itself.

Call Stack depth Waiting on
factorial_recursive(4) 1 4 * factorial_recursive(3)
factorial_recursive(3) 2 3 * factorial_recursive(2)
factorial_recursive(2) 3 2 * factorial_recursive(1)
factorial_recursive(1) 4 1 * factorial_recursive(0)
factorial_recursive(0) 5 returns 1 immediately (base case)

At the deepest point, all five frames exist in memory at once — that peak is what space complexity measures, not the total number of calls made over time. Once the base case returns 1, the stack unwinds: frame for n=1 computes 1 * 1 = 1 and returns; frame for n=2 computes 2 * 1 = 2 and returns; frame for n=3 computes 3 * 2 = 6; frame for n=4 computes 4 * 6 = 24, the final answer. The peak stack depth for input n is n + 1 frames, which is O(n) — this is exactly why recursion depth, not just the presence of loops, counts toward space complexity.

Common Mistakes

Mistake 1: Assuming recursion without an explicit data structure is O(1) space

It’s tempting to think that because this function never creates a list or dict, it must be cheap on memory:

def sum_list_recursive(numbers: list[int]) -> int:
    if not numbers:
        return 0
    return numbers[0] + sum_list_recursive(numbers[1:])

This is wrong in two ways. First, the O(n) recursion depth alone already means O(n) stack space. Second — and easy to miss — numbers[1:] creates a brand-new list at every call, copying every remaining element. For an input of length n, the slices have lengths n-1, n-2, ..., 0, and copying all of them costs O(n^2) total space and time, not O(n). The fix is to pass an index instead of slicing:

def sum_list_recursive(numbers: list[int], index: int = 0) -> int:
    if index == len(numbers):
        return 0
    return numbers[index] + sum_list_recursive(numbers, index + 1)

Now each frame stores only an integer and a reference to the same original list — O(1) extra per frame — bringing the total back down to O(n) auxiliary space, matching the recursion depth. Whenever you see slicing (numbers[1:], text[1:-1]) inside a loop or recursive call, ask whether it’s silently squaring your space and time usage.

Mistake 2: Using a mutable default argument as an accumulator

Default argument values are created once, when the function is defined — not once per call. Using a mutable default like a list means every call that doesn’t explicitly pass that argument shares the exact same object:

def collect_evens(numbers: list[int], evens: list[int] = []) -> list[int]:
    for number in numbers:
        if number % 2 == 0:
            evens.append(number)
    return evens


first_call = collect_evens([1, 2, 3, 4])
second_call = collect_evens([10, 11])
print("first_call:", first_call)
print("second_call:", second_call)

Output:

first_call: [2, 4, 10]
second_call: [2, 4, 10]

Both calls end up pointing at the same list object, so appending in the second call silently changes what looks like the first call’s already-returned result — first_call shows [2, 4, 10], not the [2, 4] a reader would expect. This isn’t just a correctness bug; it’s a memory-retention bug, since the accumulator quietly grows across unrelated calls instead of being freed. Fix it by using None as the sentinel default and allocating fresh inside the function:

from typing import Optional


def collect_evens(numbers: list[int], evens: Optional[list[int]] = None) -> list[int]:
    if evens is None:
        evens = []
    for number in numbers:
        if number % 2 == 0:
            evens.append(number)
    return evens


first_call = collect_evens([1, 2, 3, 4])
second_call = collect_evens([10, 11])
print("first_call:", first_call)
print("second_call:", second_call)

Output:

first_call: [2, 4]
second_call: [10]

Each call now gets its own fresh list, so memory doesn’t leak between unrelated calls and the results are independent, as intended.

Best Practices

  • Always state time and space complexity together — they often trade off, and interviewers usually want both.
  • Distinguish auxiliary space (extra memory beyond the input) from total space (auxiliary plus input); “space complexity” almost always means auxiliary space unless stated otherwise.
  • Remember recursion is not free: every call adds a stack frame, so deep recursion costs at least O(depth) space, and Python’s default recursion limit (around 1000) can turn very deep recursion into a RecursionError. Prefer an iterative rewrite with an explicit stack (e.g. a list or collections.deque) for large, unbounded depths.
  • Never use a mutable default argument (def f(x, acc=[])); use None and initialize inside the function body.
  • Watch for slicing (numbers[1:]) inside loops or recursive calls — each slice copies data proportional to its length and can silently turn O(n) space into O(n^2).
  • Prefer in-place mutation over building a new copy when the caller doesn’t need the original preserved, but document the side effect clearly since it changes the caller’s object.
  • Spend space deliberately: trading O(n) extra memory for a hash set or memo table is usually worth it when it turns an O(n^2) or exponential algorithm into something closer to linear.

Practice Exercises

  • Write is_palindrome(text: str) -> bool that checks whether a string reads the same forwards and backwards using O(1) extra space (not counting the input string). Hint: use two pointers starting from opposite ends instead of building a reversed copy with slicing.
  • Take a naive recursive Fibonacci function (exponential time, O(n) stack space) and rewrite it using memoization. State the new time and space complexity, and explain in one sentence what memory you spent to gain that speed.
  • Given a list of n integers, write a function that returns True if any value appears more than once, aiming for O(n) time. What space complexity does your solution need? Could you get down to O(1) extra space if you were allowed to sort the list first (destroying the original order), and what would that cost you in time?

Summary

  • Space complexity measures how memory usage grows with input size n, using the same Big-O rules as time complexity — drop constants and lower-order terms.
  • “Space complexity” usually refers to auxiliary space: extra memory used beyond the input itself, including new data structures and the recursion call stack.
  • Recursion is not automatically cheap on memory: each call adds a stack frame, so straightforward recursion costs at least O(depth) space, and Python’s recursion limit makes very deep recursion risky.
  • Hidden costs matter: slicing inside a loop or recursive call can silently turn O(n) space into O(n^2), and mutable default arguments can leak state across calls.
  • Time and space often trade off — spending extra space on a hash set or memo table can turn a quadratic or exponential algorithm into a linear or log-linear one.