Space complexity

Memory has a Big-O too — auxiliary space, recursion stacks, input space, and trade-offs. · 8 min read

Big-O usually measures time, but the same idea applies to memory. Space complexity counts the extra memory an algorithm needs as the input grows — not counting the input itself.

Input space vs auxiliary space

There are two common ways people talk about space:

Input space: the memory needed to store the input itself. An array of n numbers is O(n) input space.
Auxiliary space: extra memory the algorithm allocates while running. This is what interview questions usually mean by "space complexity".

If a function reverses an array in place, the input is O(n) but the auxiliary space is only O(1).

Common space patterns

A few variables (i, best, sum) → O(1) auxiliary space.
A copied array, set, map, or frequency table with up to n entries → O(n).
A 2D table for dynamic programming over two dimensions → often O(nm).
A queue for BFS can grow to the width of the graph/tree → O(w) or O(V).
A recursion stack stores unfinished calls → one stack frame per active call.

Recursion stack maths

Linear recursion uses linear stack space

factorial(n) calls factorial(n−1) — Only one recursive branch is active at a time.
n → n−1 → n−2 → … → 1 — The stack depth grows linearly.
n active frames in the worst moment — Each frame stores local variables and return position.

Result: O(n) space

Halving recursion uses logarithmic stack space

binary_search keeps one half — Only one recursive branch continues.
n → n/2 → n/4 → … → 1 — The stack depth is logarithmic.
depth = log₂ n — One frame per level.

Result: O(log n) space if recursive, O(1) if iterative

The trade-off

Often you can spend memory to save time. Two-sum is O(n²) by brute force, but remembering seen values in a hash set makes it O(n) time for O(n) space. Knowing both axes lets you pick the right balance.

Space-saving tricks

A few patterns show up again and again:

Use two pointers instead of making a reversed copy.
Store counts instead of full lists when only frequencies matter.
Roll a DP table from O(nm) down to O(m) when each row only depends on the previous row.
Prefer an iterative loop over recursion when stack depth might become large.
Stream data one item at a time when you do not need the whole input in memory.