Space Complexity

complexity-theory

Definition

Space Complexity

The space complexity of an algorithm is a function that bounds the amount of memory it uses in terms of the length of the encoded input.

Formally, fix an encoding of problem instances. For an instance $I$, let

$$m(I)=|I|$$

be the number of symbols in the encoded input. The worst-case space complexity of an algorithm $A$ is the function

$$S_A(n)=\max \{{\mathrm{space}}_A(I)\mid |I|=n\}.$$

Thus, space complexity measures how memory usage grows as the encoded input length grows.

Encoding

Space complexity is measured relative to an encoding, just like time complexity. A numeric value may be much larger than its encoded length.

For example, a capacity $W$ written in binary has length $\Theta (\log W)$, while storing a table with one cell for every value $0,1,\dots ,W$ uses $\Theta (W)$ space.

This is why pseudo-polynomial dynamic programming can also have pseudo-polynomial space usage: the table can be polynomial in the numeric values, but exponential in the binary input length.

Polynomial Bound

An algorithm uses polynomial space if there exist fixed constants $C,c$ such that, for every instance $I$,

$${\mathrm{space}}_A(I)\le C\cdot |I{|}^c.$$

The exponent $c$ is fixed for the algorithm. It cannot depend on the instance.

Examples

Dynamic programming table

A knapsack-style dynamic programme with table entries $T[i,w]$ for $0\le i\le n$ and $0\le w\le W$ uses

$$O(nW)$$

table cells.

If $W$ is encoded in binary, then $W\approx 2^{{\ell }_W(I)}$, where ${\ell }_W(I)=\lceil {\log }_2(W+1)\rceil$. Hence the space usage may be exponential in the encoded length of $W$.

If $W$ is encoded in unary, the input length is already $\Theta (W)$, so the same table size is polynomial in the input length.