Space Complexity

What space complexity measures

Space complexity describes how the memory an algorithm needs grows as a function of the input size, usually written n. It is expressed in Big-O notation, the same asymptotic upper bound used for running time; the time-complexity topic owns how that notation works, so here the focus is strictly on memory. NIST's Dictionary of Algorithms and Data Structures defines complexity broadly as the minimum resources needed to solve a problem, and explicitly lists memory alongside time as one of those resources, so Big-O applies to space just as naturally as it does to speed.

Total space has two parts: the input space (the memory already occupied by the data you were handed) plus the auxiliary space (any extra working memory the algorithm allocates while it runs). Because every algorithm must at least hold its input, the input term is often the same across competing methods and tells you little about which is more efficient. So when people compare algorithms by 'space,' they almost always mean auxiliary space: the extra beyond the input. An algorithm that reads a list of n numbers and keeps just a running total uses O(1) auxiliary space, even though the input itself occupies O(n).

In-place algorithms and O(1) auxiliary space

An in-place algorithm transforms its input using only a constant amount of auxiliary memory, no matter how large the input is. NIST describes an in-place sort as one in which the sorted items occupy the same storage as the original ones, keeping at most a constant number of items in auxiliary memory at any time. Reversing an array by swapping the two ends and working inward is the canonical example: it needs only a couple of index variables and one temporary slot for each swap, so its auxiliary space is O(1) regardless of length.

The contrast is an approach that builds a brand-new structure. Reversing by copying elements into a freshly allocated array of the same length uses O(n) auxiliary space, because the extra memory grows in step with the input. Both versions are O(n) in time, but they differ sharply in memory, and on a large or memory-constrained input that difference decides whether the program completes. In-place methods trade a little algorithmic convenience for a large saving in memory; the cost is that they overwrite (mutate) the original data, which is not always acceptable.

Common space costs and recursion

A few patterns cover most cases. O(1) auxiliary space means a fixed handful of variables whose count does not depend on n. O(n) auxiliary space means allocating a copy, a lookup table, or another structure that scales with the input. Recursion introduces a subtler cost. Each call that has not yet returned occupies a frame on the call stack, storing that call's local variables and the address to return to. A recursion that reaches depth d therefore holds up to d frames at once, giving O(d) auxiliary space even if each individual call does almost nothing. For a simple linear recursion over n items, d is proportional to n, so the stack cost is O(n).

This space is real and bounded. Python, for instance, caps the interpreter stack; its documentation notes the limit exists to prevent infinite recursion from overflowing the underlying C stack and crashing the interpreter. Exceed it and the program raises a RecursionError rather than silently corrupting memory. An iterative loop over the same data usually keeps only a few variables, so converting deep recursion to iteration is a standard way to cut O(n) stack space down to O(1).

The time-space trade-off

Time and space are often exchangeable, and recognizing the trade-off is a core design skill. Spending memory can buy speed: to test whether any two values in a list add up to a target, storing the values already seen in a hash set uses O(n) auxiliary space but finishes in about O(n) time, whereas a nested-loop scan uses O(1) auxiliary space but takes O(n squared) time. Lookup tables, caches, and precomputed indexes all follow the same logic, trading memory to avoid repeated work. The trade also runs the other way: an in-place algorithm gives up scratch space to stay within a tight memory budget, sometimes accepting more complex logic or a constant-factor slowdown in return. There is no universally correct choice. The right decision depends on which resource is scarce for your problem: the size of the data, the memory available on the target machine, and how often the operation runs. Analyzing both dimensions, rather than time alone, is what lets you make that call deliberately instead of by accident.