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 , let

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

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 written in binary has length , while storing a table with one cell for every value uses 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 such that, for every instance ,

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

Examples

Dynamic programming table

A knapsack-style dynamic programme with table entries for and uses

table cells.

If is encoded in binary, then , where . Hence the space usage may be exponential in the encoded length of .

If is encoded in unary, the input length is already , so the same table size is polynomial in the input length.