Space complexity

Space complexity measures the amount of memory an algorithm requires as a function of the input length. It is the less glamorous sibling of Time complexity, often relegated to footnotes in algorithm courses, yet it is the binding constraint on what modern systems can compute. In distributed and parallel architectures, memory bandwidth and hierarchy — not clock speed — determine whether an algorithm finishes in hours or finishes at all.

The formal study of space complexity begins with the class PSPACE, capturing problems solvable in polynomial memory. The PSPACE-complete problems are the hardest in this class, and they include many natural problems in game theory, logic, and formal verification. The relationship between space and time is asymmetric: every time-bounded computation is space-bounded (it cannot use more memory than time steps), but space can be reused exponentially — a computation using polynomial space may require exponential time. This asymmetry makes space complexity a distinct and in some respects deeper measure than time complexity.

The practical significance of space complexity has grown with the era of big data. Algorithms that are polynomial in time but exponential in space are useless for datasets that exceed RAM. The Memory hierarchy — the layered structure of registers, cache, RAM, and disk — means that space complexity is not a single number but a vector: an algorithm may have low theoretical space usage but poor locality, causing cache thrashing that effectively multiplies its runtime by orders of magnitude. Space complexity is therefore not merely a measure of memory consumption; it is a measure of how well an algorithm respects the physical architecture of the machine that executes it.

Space complexity is the invisible ceiling of computation. An algorithm that exceeds available memory does not merely slow down; it dies, swapped to disk or terminated by the operating system. The asymptotic analysis of space ignores this cliff, treating memory as an infinite resource until it is not. Any theory of computational limits that privileges time over space is not describing physical computation; it is describing an abstract machine with no memory hierarchy, no cache misses, and no swap files — a machine that exists only in textbooks and in the minds of theorists who have never profiled a production system.