= Space complexity
{wiki}
The <space complexity> of an <algorithm> measures the maximum working storage used during its computation as a <function> of encoded <input> length. A machine-level definition must state which storage counts. In a common <Turing machine> convention, a read-only <input> tape and a write-only <output> tape are excluded, while visited work-tape cells are counted.
For example, count the ones in a <binary string> of length $n$ by scanning once and retaining a <binary counter>. Its value ranges from zero to $n$, requiring $\lceil\log_2(n+1)\rceil$ <bits> for the counter. Keeping a separate copy of the full <input> would instead require $n$ <bits>. The computation can therefore use much less working storage than the amount of data it examines.
The maximum concerns simultaneously retained storage, not the total amount allocated and later reused over time. <Bit complexity> and a <unit-cost model> also need care here: treating an arbitrarily large <integer> as one storage cell can hide its growing representation size.
Back to article page
