Space Complexity

Space complexity measures how much working memory an algorithm needs as a function of input size.

Memory as a resource

Space complexity counts the memory cells an algorithm uses beyond the input itself, as a function of input size n. Like time, it is stated asymptotically. Memory can be the binding constraint even when time is fine, especially for large data sets that must fit in a fixed machine.

Auxiliary versus total space

Total space includes the input; auxiliary space counts only the extra working memory an algorithm allocates. An in-place sort uses O(1) auxiliary space, while merge sort needs O(n) extra for its temporary arrays. When people say an algorithm is "in place," they mean small auxiliary space.

The time-space tradeoff

Time and space can often be traded against each other. Caching results (memoization) spends memory to save time; recomputing values spends time to save memory. Choosing the balance depends on which resource is scarce for the target machine and problem size.

• O(1) space: a few counters, regardless of n
• O(log n) space: recursion depth of binary search
• O(n) space: a copy of the input or a hash table
• O(n^2) space: a full pairwise matrix

Space complexity classes

Just as time defines P, space defines classes like L (logarithmic space) and PSPACE (polynomial space). A striking fact is that PSPACE contains both P and NP: with polynomial memory and enough time you can solve any NP problem by exhaustively trying solutions, reusing space across attempts.

A worked contrast

Computing the nth Fibonacci number recursively without memoization uses O(n) stack space and exponential time. An iterative version keeps only the last two values, using O(1) space and O(n) time. Same output, radically different memory footprint, illustrating how algorithm structure sets space cost.