Space Complexity: RAM Matters Too

Time complexity gets most of the attention, but space complexity — how much memory an algorithm consumes — is equally important in production systems and interviews. Memory is finite. Running out of RAM crashes a process; running out of CPU just makes it slow.

What Counts as "Extra" Space?

Space complexity measures the additional memory the algorithm allocates beyond the input itself. The input is already in memory; we're measuring what the algorithm adds on top.

1. Scalar variables: A single integer counter is $O(1)$ — constant space regardless of input size.
2. Data structures proportional to input: Creating a new array, list, or hash map of size N is $O(N)$.
3. The call stack (recursion): Every function call occupies a stack frame in memory. If a recursive function calls itself N times before any call returns, the call stack holds N frames simultaneously — $O(N)$ space. This is the most commonly forgotten source of space complexity.

Concrete Example

# Function A: In-place sort (modifies the original array)
# Space: O(1) — no new data structures created
def sort_in_place(arr):
    arr.sort()  # Python's Timsort modifies arr directly
    return arr

# Function B: Sort a copy (preserves the original)
# Space: O(N) — a new array of size N is allocated
def sort_copy(arr):
    return sorted(arr)  # Creates and returns a new list

Both functions have the same time complexity ($O(N \log N)$), but Function A uses constant extra space while Function B uses linear extra space. On an embedded device with 256KB of RAM processing a 100,000-element array, Function B could cause an out-of-memory crash.

The Time-Space Trade-off

Many optimizations trade space for time. A hash map lookup is $O(1)$ time but requires $O(N)$ space to store the map. Memoization (caching recursive results) reduces time from $O(2^N)$ to $O(N)$ but requires $O(N)$ space for the cache. In interviews, always state both complexities and be ready to discuss the trade-off.