Space Complexity

Space complexity is a measure of the memory required by an algorithm as a function of its input size. Together with time complexity, it is a fundamental resource measure in computational complexity. Whereas time counts computational steps, space counts storage used during execution. The quantity measured depends on the computational model and on whether input, output, and temporary storage are included. (ocw.mit.edu)

Definition and asymptotic notation

For an algorithm $A$, let $s_A(x)$ denote its space usage on input $x$. Its worst-case space complexity is

where $|x|$ denotes input size. Depending on the problem, size may mean the number of input elements or the length of their encoded representation. This definition distinguishes the resources used on a particular input from the maximum required across inputs of the same size. (cs.uwaterloo.ca)

Space bounds are commonly expressed using asymptotic notation. An $O(n)$ bound means memory usage is eventually bounded above by a constant multiple of $n$; a $\Theta(n)$ bound gives matching upper and lower growth rates. Common orders include constant, logarithmic, linear, and quadratic space. Asymptotic analysis suppresses constant factors, whereas concrete memory analysis counts the storage occupied by values, references, and objects. (algs4.cs.princeton.edu)

What counts as space

Auxiliary space is additional working storage beyond the input representation. A total-space analysis includes the input and any other storage covered by its stated convention. Thus, an algorithm processing an existing $n$-element array may use constant auxiliary space even though the array itself occupies linear space. Output accounting also needs to be specified: excluding externally written output differs from retaining a result in memory. (cs.cornell.edu)

Algorithmic memory analysis generally concerns the maximum storage needed simultaneously, not the sum of every allocation made throughout execution. Memory released and reused need not be counted repeatedly. The analysis must include temporary objects, retained data structures, and active procedure calls. Passing a reference to an existing array does not itself copy that array; constructing a new array does. (courses.cis.cornell.edu)

In Turing-machine models used to study small space bounds, the input is commonly placed on a read-only tape, while writable work-tape cells are counted. A separate write-only output tape may also be excluded. These conventions make sublinear working-space bounds meaningful despite the input’s physical storage requirements. (courses.cs.cornell.edu)

Computational models and units

Space may be measured in bits, bytes, tape cells, or machine words. In the word-RAM model, memory consists of addressable words containing $w$ bits. An algorithm using $k$ words therefore occupies $kw$ bits for those words; the two units should not be treated as interchangeable without specifying $w$. (ocw.mit.edu)

For example, an index ranging over $n$ positions needs $\Theta(\log n)$ bits, although it may occupy one machine word. Consequently, “constant space” in a word-based analysis can involve a growing number of bits. Arbitrarily large integers likewise cannot automatically be counted as constant-size objects: their encoded length depends on their magnitude. (cs.cmu.edu)

Concrete memory requirements also depend on representation choices and the programming language implementation. References, object headers, and alignment padding contribute storage beyond the represented values. These costs can matter substantially even when they do not change an asymptotic bound. (algs4.cs.princeton.edu)

Recursion and representative algorithms

Recursion consumes memory through the call stack. If each active call needs constant space and the maximum recursion depth is $d$, stack space is $O(d)$. The total number of calls is not the relevant quantity: calls executed sequentially can reuse storage. Transforming suitable recursive code into iteration can eliminate the growing stack; automatic tail-call optimization is implementation-dependent. (courses.cis.cornell.edu)

In graph traversal, a conventional depth-first search maintains visited-state information and an explicit or recursive traversal stack. With $V$ vertices, its auxiliary space is $O(V)$, excluding the graph representation. A search may perform extensive work while retaining only its current traversal state rather than its entire execution history. (cs.cornell.edu)

A standard array-based merge sort illustrates a different source of memory use. Its divide-and-conquer structure has logarithmic recursion depth, but its merging buffer occupies $\Theta(n)$ extra space. The overall auxiliary bound is therefore linear, not logarithmic. This bound describes the particular implementation rather than every possible method of merging or sorting. (algs4.cs.princeton.edu)

Time–space trade-offs

A time–space trade-off occurs when retaining information avoids later computation, or recomputing information reduces retained storage. Memoization, often used in dynamic programming, stores previously computed results so that repeated subproblems can be answered by lookup. It can substantially reduce repeated recursive work, but the stored results contribute to memory usage. (cs.cornell.edu)

Space can also be reused across successive stages. In space-bounded simulations, sequential recursive searches may share working storage even when the number of computational steps is very large. This reuse is one reason time and space bounds can differ markedly. (courses.cs.cornell.edu)

Space complexity classes

The class $\mathrm{DSPACE}(s(n))$ contains decision problems solvable deterministically within $O(s(n))$ working space; $\mathrm{NSPACE}(s(n))$ is its nondeterministic counterpart. PSPACE permits polynomial space, while NPSPACE permits nondeterministic polynomial space. Here “polynomial” concerns the memory bound, not necessarily the running time. (ocw.mit.edu)

Savitch’s theorem establishes, under standard assumptions for space bounds at least logarithmic,

Its simulation trades potentially extensive computation for a controlled increase in storage. Because squaring a polynomial preserves polynomial growth, the theorem implies $\mathrm{PSPACE}=\mathrm{NPSPACE}$. (courses.cs.cornell.edu)