Space Complexity

What Is Space Complexity?

Space complexity measures how much memory an algorithm uses as a function of its input size. Like time complexity, it uses asymptotic notation (Big-O) and focuses on growth rate, not exact bytes.

There are two components to consider:

• Input space — memory consumed by the input itself
• Auxiliary space — extra memory the algorithm allocates beyond its input

When engineers refer to the space complexity of an algorithm, they typically mean auxiliary space — because the input is given to you regardless of the algorithm you choose.

O(1) — Constant Space

The algorithm uses a fixed amount of extra memory regardless of input size.

def sum_array(arr):
    total = 0               # one variable
    for val in arr:
        total += val
    return total

No matter how large arr is, this function allocates only one extra variable (total). Space: O(1).

def reverse_in_place(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1

Two pointers, no extra array. Space: O(1). This contrasts with creating a new array to hold the reversed result (O(n)).

O(n) — Linear Space

The algorithm allocates memory proportional to the input size.

def copy_array(arr):
    result = []
    for val in arr:
        result.append(val)
    return result

result grows with the input — O(n) space.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Merge sort creates temporary arrays at each merge step. The total auxiliary space across all levels of recursion is O(n) — even though O(log n) stack frames exist simultaneously, the merge buffers at each level together sum to O(n).

Stack Space and Recursion

Every function call occupies a stack frame — a block of memory that stores local variables, the return address, and parameters. Recursive algorithms can consume significant stack space.

Depth = Stack Space

The space used by recursion equals the maximum depth of the call stack, multiplied by the constant space per frame.

Linear recursion:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(n) creates n stack frames simultaneously before any return. Stack space: O(n).

factorial(5)
  factorial(4)
    factorial(3)
      factorial(2)
        factorial(1)  ← bottom of stack

Logarithmic recursion:

def binary_search(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

Binary search halves the search space at each level. Maximum depth: log n. Stack space: O(log n).

Tree recursion:

def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

Even though this creates O(2ⁿ) total calls, at any point in time the maximum depth of the call stack is O(n). Stack space: O(n).

The time complexity is O(2ⁿ); the space complexity is O(n). These can differ — and this is common in tree recursion.

Iterative vs Recursive: A Space Comparison

The same logic can often be written iteratively (O(1) stack space) or recursively (O(n) or O(log n) stack space).

Fibonacci — naive recursion: Time O(2ⁿ), Space O(n)

def fib_recursive(n):
    if n <= 1: return n
    return fib_recursive(n-1) + fib_recursive(n-2)

Fibonacci — iterative: Time O(n), Space O(1)

def fib_iterative(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Fibonacci — memoized (top-down DP): Time O(n), Space O(n)

def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Memoization trades space for time. Iteration gives you the best of both when no branching is needed.

O(n²) and Higher Space Complexities

Some algorithms require storing a two-dimensional structure.

2D DP table:

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # O(m * n) space
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

The DP table has m × n entries. Space: O(m × n).

This can often be optimized. Since each row only depends on the previous row, you can use two rolling arrays:

def lcs_optimized(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, [0] * (n + 1)
    return prev[n]

Space reduced from O(m × n) to O(n). The time complexity stays O(m × n).

Heap Space vs Stack Space

Memory is divided into two regions relevant to algorithms:

Recursive algorithms risk stack overflow if the depth is too large (e.g., recursing over millions of elements). Iterative algorithms using explicit stacks (on the heap) avoid this.

Space-Time Tradeoffs

Many algorithmic improvements trade space for time.

Hash set for deduplication:

# O(n²) time, O(1) auxiliary space
def has_duplicate_slow(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False
 
# O(n) time, O(n) auxiliary space
def has_duplicate_fast(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return True
        seen.add(val)
    return False

Storing previously seen values in a hash set costs O(n) space but brings time from O(n²) to O(n).

Caching (memoization) is the general form of this tradeoff. You pay memory to avoid redundant computation.

Analyzing Space Complexity: A Checklist

When determining the space complexity of an algorithm, ask:

1. What extra data structures are allocated? Arrays, hash maps, sets, trees.
2. What is the maximum recursion depth? Each frame is O(1) per call for simple functions.
3. Are there temporary arrays inside loops? If you allocate O(n) inside an O(n) loop, that might be O(n²) total — or O(n) if each allocation replaces the previous one.
4. What is the output size? Sometimes output is included in space complexity, sometimes excluded. Clarify which convention is being used.

Summary

Key principles:

• Recursion depth determines stack space
• Iterative approaches often reduce space at no time cost
• Trading O(1) → O(n) space can reduce time from O(n²) → O(n)
• For DP: check if you can use rolling arrays to reduce 2D to 1D space

Next: Master Theorem — a formula for solving recurrence relations in divide-and-conquer algorithms.