Space Complexity

March 2026 · 18 min read

Time complexity gets all the attention, but space complexity is equally important. Memory is finite, and for large inputs, the algorithm that uses less memory might be the only one that's feasible.

What Counts as Space?

Space complexity measures the maximum amount of memory used at any point during execution, as a function of input size.

Auxiliary space vs. total space

Auxiliary space: Extra memory used beyond the input. This is what we usually mean.
Total space: Auxiliary + the input itself.

When someone says "merge sort uses $O(n)$ space," they mean auxiliary. The input is always $O(n)$.

What we count

Variables and pointers: $O(1)$ each.
Arrays, vectors, hash maps: $O(\text{elements stored})$.
Recursion: each stack frame costs $O(1)$ (or more if local arrays). Max recursion depth × frame size.
Dynamically allocated objects.

Recursion and Stack Space

Every recursive call pushes a stack frame containing local variables, parameters, and a return address. The maximum number of frames on the stack at once = the maximum recursion depth.

Example 1: Factorial — $O(n)$ space

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // each call adds a frame
}

Recursion depth = $n$. Each frame has $O(1)$ variables. Space: $O(n)$.

Example 2: Binary search — $O(\log n)$ space (recursive)

int bsearch(vector<int>& a, int lo, int hi, int t) {
    if (lo > hi) return -1;
    int mid = (lo + hi) / 2;
    if (a[mid] == t) return mid;
    if (a[mid] < t) return bsearch(a, mid+1, hi, t);
    return bsearch(a, lo, mid-1, t);
}

Only one branch recurses (tail-like). Depth = $O(\log n)$. Space: $O(\log n)$.

The iterative version uses $O(1)$ space, no stack frames at all.

Example 3: Post-order tree traversal — $O(h)$ space

void postOrder(TreeNode* node) {
    if (!node) return;
    postOrder(node->left);   // active frames: depth = current level
    postOrder(node->right);
    visit(node);
}

Max recursion depth = tree height $h$. For a balanced tree, $h = O(\log n)$. For a skewed tree, $h = O(n)$.

Common Space Complexity Patterns

Algorithm	Time	Auxiliary Space	Notes
Linear search	$O(n)$	$O(1)$	Just a loop variable
Binary search (iterative)	$O(\log n)$	$O(1)$	lo, hi, mid
Binary search (recursive)	$O(\log n)$	$O(\log n)$	Stack frames
Merge sort	$O(n \log n)$	$O(n)$	Merge buffer
Quicksort	$O(n \log n)$	$O(\log n)$	Stack; $O(n)$ worst case
Heap sort	$O(n \log n)$	$O(1)$	In-place
BFS	$O(V + E)$	$O(V)$	Queue can hold entire level
DFS (recursive)	$O(V + E)$	$O(V)$	Stack = recursion depth
Dynamic programming (2D)	$O(nm)$	$O(nm)$	Full DP table
DP (space-optimized)	$O(nm)$	$O(m)$	Keep only 2 rows

In-Place Algorithms

An algorithm is in-place if it uses $O(1)$ auxiliary space (ignoring the input). Examples:

Heap sort: Builds a heap in the array itself. Sorts by repeatedly extracting the max.
Quicksort (iterative, with O(log n) stack optimization): Partitions in-place.
Reversing an array: Two pointers swapping from ends toward the middle.
Dutch national flag (3-way partition): O(1) extra space.

// In-place array reversal: O(1) auxiliary space
void reverse(vector<int>& arr) {
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        swap(arr[l], arr[r]);
        l++; r--;
    }
}

The Space-Time Trade-off

Often you can trade space for time or vice versa:

Approach	Time	Space	Example
No precomputation	High (recompute)	$O(1)$	Recompute Fibonacci every time
Memoization	Low (lookup)	$O(n)$	Cache Fibonacci in array
Hash table	$O(1)$ query	$O(n)$	Two-sum: store complements
Brute force search	$O(n)$ query	$O(1)$	Two-sum: nested loops
Sorting + binary search	$O(\log n)$ query	$O(1)$ if sortable	Middle ground

Design principle: If the problem allows it, precompute and cache results (use more space) to speed up future queries. If memory is constrained, recompute on the fly.

DP Space Optimization Technique

Many 2D DP problems only need the current and previous row. Instead of maintaining the full table ($O(nm)$), keep just 2 rows ($O(m)$):

// Longest Common Subsequence: O(m) space instead of O(nm)
int lcs(string& a, string& b) {
    int n = a.size(), m = b.size();
    vector<int> prev(m + 1, 0), curr(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1])
                curr[j] = prev[j-1] + 1;
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }
    return prev[m];
}

Time remains $O(nm)$ but space drops from $O(nm)$ to $O(m)$. This technique works whenever $dp[i][j]$ depends only on $dp[i-1][\cdot]$ and $dp[i][j-1]$.

Tail Recursion and Space

A function is tail-recursive if the recursive call is the last thing it does. Some compilers optimize tail calls to reuse the current stack frame, converting $O(n)$ stack space to $O(1)$.

// Not tail-recursive: must multiply after return
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // multiplication AFTER recursive call
}

// Tail-recursive version
int factHelper(int n, int acc) {
    if (n <= 1) return acc;
    return factHelper(n - 1, n * acc);  // nothing after recursive call
}

C++ does not guarantee tail-call optimization, but many compilers (GCC, Clang with -O2) do it.

Summary

Space complexity = maximum memory used at any point during execution.
Auxiliary space = extra memory beyond the input. Usually what we report.
Recursion costs stack space proportional to the maximum depth.
In-place algorithms use $O(1)$ auxiliary space.
The space-time trade-off is everywhere: memoization, hash tables, precomputation.
DP space optimization: keep only the rows/columns you need, reducing $O(nm)$ to $O(m)$.