Measuring Space Complexity

Space complexity asks: as a function of input length $n$, how many tape cells does a Turing machine need to visit before it halts? This is a fundamentally different question from time complexity, because tape cells can be overwritten and reused, while time steps cannot be "reused" — each step happens once. A machine that runs for $2^n$ steps might still use only $\log n$ cells of memory, revisiting and rewriting the same small region over and over. This is precisely the phenomenon complexity theory wants to isolate and measure. To make sublinear space meaningful, we adopt a specific machine model: a multi-tape Turing machine with a read-only input tape and one or more separate, read-write work tapes. The input tape's head can move but can never write; the work tape is where all computation and storage happens, and it is the only tape whose usage counts toward the space bound. Without this separation, "space" would trivially be at least $n$ for any machine that has to read all $n$ input symbols, since in a single-tape model reading the input already uses $n$ cells. By quarantining the input on its own read-only tape, we allow the interesting resource — genuine working memory — to be smaller than the input itself, all the way down to $O(\log n)$ in useful cases. Formally, for a function $f: \mathbb{N} \to \mathbb{N}$, we define the space complexity of a Turing machine $M$ that halts on all inputs as the function $f(n) =$ the maximum number of work-tape cells $M$ visits, maximized over all inputs of length $n$. The class

collects all languages decidable within that space bound. This is the direct analogue of $\mathrm{TIME}(f(n))$ from Measuring Time Complexity, with "steps" replaced by "distinct cells visited on the work tape." The nondeterministic analogue $\mathrm{NSPACE}(f(n))$ is defined the same way but for nondeterministic Turing machines, where we require every branch of the computation to respect the space bound (equivalently, since we only care about accepting/rejecting behavior, that the machine never uses more than $O(f(n))$ cells on any branch it explores before halting).

The machine model, precisely. A space-bounded Turing machine $M$ has:

• a read-only input tape holding the input string $w$ of length $n$, bracketed by endmarkers, with a head that moves left/right but never writes;
• one or more read-write work tapes, initially blank, where $M$ performs all its computation;
• a finite control with states, exactly as in an ordinary Turing machine.

The space used on a given input is the number of distinct cells on the work tape(s) that the head ever visits during the run (for multiple work tapes, sum the cells used across tapes, or equivalently track the largest single tape needed and lose only a constant factor). We define

and say $M$ runs in space $f(n)$. As with time complexity, we use big-$O$ to suppress model-dependent constants: $\mathrm{SPACE}(f(n))$ is the set of languages decided by some machine using $O(f(n))$ space on inputs of length $n$.

Why the read-only input tape is essential. Consider a machine that must merely check parity of the number of 1s in a bit string of length $n$. On a single-tape machine, the head has already swept across all $n$ input cells — under a model where "space" means "cells visited, period," this machine trivially uses $\Omega(n)$ space no matter how clever it is, because reading the input costs $n$. By moving the input onto a separate tape that is not counted, the same algorithm — sweep once, keep a single bit "parity so far" on the work tape — is revealed to use only $O(1)$ space. This is the entire point of the convention: it isolates genuine working memory from the unavoidable cost of reading the problem statement.

A configuration and why space bounds control everything. A configuration of a space-bounded machine records: the current state, the position of the input head, the entire contents of all work tapes, and the positions of all work-tape heads. This is exactly analogous to a configuration in the time-complexity setting, but now the crucial fact is: > If a machine uses at most $f(n)$ work-tape space, the number of distinct configurations is bounded — and if a machine ever revisits the same configuration twice, it is in an infinite loop. This single observation is the engine behind almost every theorem about space complexity, including the time bound derived below and (later) Savitch's Theorem and the Space Hierarchy Theorem.

Counting configurations. Suppose $M$ has $|Q|$ states, work-tape alphabet size $|\Gamma|$, uses at most $f(n)$ cells on one work tape, and the input has length $n$ (so the input head has $n$ possible positions, or $n+2$ counting endmarkers). Then the number of distinct configurations is at most

since we choose a state ($|Q|$ ways), an input-head position ($O(n)$ ways), work-tape contents ($|\Gamma|^{f(n)}$ ways), and a work-tape head position ($f(n)$ ways). Because this is finite, a deciding machine that never repeats a configuration must halt within this many steps — otherwise, by pigeonhole, it would revisit a configuration and loop forever, contradicting the assumption that it halts on every input. ``` // Pseudocode: the space-complexity accounting used to derive // the time bound for an f(n)-space-bounded machine M. function ConfigurationBound(Q, Gamma, n, f_n): // number of possible states states = |Q| // number of positions for the read-only input head input_pos = n + 2 // includes both endmarkers // number of possible contents of the work tape (length f_n) tape_content = |Gamma| ^ f_n // number of positions for the work-tape head tape_pos = f_n return states input_pos tape_content * tape_pos // Consequence used throughout space-complexity theory: // If M halts on every input, then on inputs of length n, // M runs in at most ConfigurationBound(Q, Gamma, n, f(n)) steps, // because repeating a configuration would force an infinite loop. ``` ``` // Pseudocode: generic template for a space-bounded decider, // illustrating what "space used" means operationally. function DecideWithBoundedSpace(w): n = length(w) input_head = 0 // read-only, moves over w only work_tape = [] // read-write, grows only as touched state = q_start while state not in {q_accept, q_reject}: input_symbol = w[input_head] // read-only access work_symbol = read(work_tape, work_head) (state, new_work_symbol, move_input, move_work) = transition(state, input_symbol, work_symbol) write(work_tape, work_head, new_work_symbol) input_head += move_input // -1, 0, or +1 work_head += move_work // -1, 0, or +1 // SPACE USED so far = number of distinct work_head // positions visited; input_head movement is NOT counted. return (state == q_accept) ```

Space usage is well-defined and monotone in the right sense. Because $M$ is required to halt on every input (we only define space complexity for deciders, exactly as with time complexity), the maximum in $f(n) = \max_{|w|=n} \text{space}(M, w)$ is a well-defined finite number for each $n$: every computation on a fixed input is finite, so it visits finitely many cells, and there are finitely many inputs of length $n$.

The fundamental space-to-time bound. This is the central quantitative fact of the theory: > Claim. If $M$ decides a language in $O(f(n))$ space, with $f(n) \geq \log n$, then $M$ runs in $2^{O(f(n))}$ time. Proof sketch. From the configuration count above, the number of distinct configurations reachable on an input of length $n$ is at most

Since $f(n) \geq \log n$ (a standard convention that avoids degenerate sub-logarithmic cases), the factor $n = 2^{\log n} \le 2^{f(n)}$, so every polynomial factor in $n$ and $f(n)$ is absorbed into $2^{O(f(n))}$. Hence $c(n) = 2^{O(f(n))}$. Because $M$ halts on every input, it can never revisit the same configuration — if it did, it would repeat that configuration's entire future forever, contradicting halting. So the number of steps before halting is at most the number of distinct configurations, giving a running time of $2^{O(f(n))}$. $\blacksquare$ This proves the inclusion

which is the space-complexity analogue of the trivial time-hierarchy fact that more time gives strictly more power — except here it runs the other direction, bounding time by space. It is the technical seed from which the containment $\mathrm{PSPACE} \subseteq \mathrm{EXPTIME}$ and, ultimately, statements like $\mathrm{NL} \subseteq \mathrm{P}$ are grown.

Time bounds space, too — but weakly. In the reverse direction, if $M$ runs in $t(n)$ time, it visits at most $t(n)$ work-tape cells (it can write to at most one new cell per step), so

Combined with the bound above this gives $\mathrm{TIME}(t(n)) \subseteq \mathrm{SPACE}(t(n)) \subseteq \mathrm{TIME}(2^{O(t(n))})$ — a coarse but honest sandwich showing space is a strictly weaker resource in the sense that "small space" can hide "large time," but not vice versa.

Sublinear space is meaningful precisely because of the read-only convention. With input read-only, the classes of real interest emerge:

$\mathrm{L}$ and $\mathrm{NL}$ (foreshadowed here, developed fully elsewhere) capture problems solvable with only logarithmically many work cells — enough to store a constant number of pointers into the input, but not enough to copy the input itself. This is only a coherent idea because the input tape does not count; if it did, $\log n$ space would be impossible for any machine that must inspect all $n$ symbols.

Correctness of the model itself. The "correctness" claim to verify here is that the definitions compose sensibly: (1) space usage does not depend on which of two "reasonable" multi-tape encodings we pick, up to a constant factor, exactly as with time complexity's linear speedup theorem, and (2) closure under complement is free for space classes in a way it is not (known to be) for time classes — flipping accept/reject states, or in the nondeterministic case appealing to the (deferred) Immerman–Szelepcsényi theorem, preserves the space bound exactly, since no extra memory is needed to swap accept and reject. These structural facts are what make space complexity, despite looking like a minor variant of time complexity, behave quite differently — a difference that becomes sharp with Savitch's Theorem.

Honest tradeoffs. The model is powerful precisely because it under-counts a real cost: a machine using $O(\log n)$ space still spends time proportional to at least $n$ just moving its input head across the input, and typically far more (often polynomial, sometimes exponential, per the bound above) doing its computation. "Low space" is not "fast" — it is a genuinely different axis, and the entire point of this article is to keep that axis cleanly separated from time.

Consider the language

strings that read the same forwards and backwards. We build a machine using only $O(\log n)$ space — sublinear, since the input itself has length $n$ — by keeping just two pointers (indices) into the input on the work tape, rather than copying any of the input. ``` function IsPalindrome(w): // w given on read-only input tape, length n i = 0 // left pointer, stored on work tape in binary j = n - 1 // right pointer, stored on work tape in binary while i < j: a = w[i] // move input head to position i, read symbol b = w[j] // move input head to position j, read symbol if a != b: reject i = i + 1 j = j - 1 accept ```

Why this uses only $O(\log n)$ space. The only information stored on the work tape is the pair of pointers $i$ and $j$, each an integer between $0$ and $n-1$. Writing an integer up to $n-1$ in binary takes $\lceil \log_2 n \rceil$ bits, so storing both pointers takes $O(\log n)$ work-tape cells — nothing else is ever written. The input itself is never copied; the machine repositions its (uncounted) input-tape head to whatever position $i$ or $j$ currently names, reads one symbol, and discards it. Let us trace this on $w = \texttt{abaaba}$ reversed appropriately — take $w = \texttt{110011}$ ($n = 6$), which is a palindrome, and $w' = \texttt{110010}$, which is not.

Work-tape contents used across the whole run: only the six bit-triples needed to represent $i \in \{0,1,2,3\}$ and $j\in\{5,4,3\}$ — at most $2\lceil \log_2 6\rceil = 6$ bits total, i.e. $O(\log n)$, regardless of how large $n$ grows (the constant 6 would grow only logarithmically with $n$). Now trace the non-palindrome $w' = \texttt{110010}$ ($n = 6$):

The machine halts immediately at step 0 with a reject, having used the same $O(\log n)$-bit budget for the pointers, confirming that the space bound does not depend on whether the string happens to be a palindrome — it is a worst-case guarantee, the way it must be for the definition of $\mathrm{SPACE}(f(n))$ to make sense.

Contrast with time. This algorithm runs in $O(n)$ time (it makes $O(n)$ comparisons, each requiring the input head to reposition, costing up to $O(n)$ moves per repositioning in the worst tape layout — so time here is $O(n^2)$ in the crudest analysis, or $O(n)$ with a smarter dual-head implementation). The point of the example is not to optimize time but to demonstrate: a language that visibly requires reading all $n$ input symbols can still be decided using only $O(\log n)$ work-tape space, which is the entire content of the read-only-input convention.

The formal study of space as a resource distinct from time grew out of the same 1960s program that gave rise to time-complexity classes, but its most distinctive results — the relationship between deterministic and nondeterministic space, and the space hierarchy — came slightly later and required new proof techniques specific to the reusability of memory.

Space complexity is not an abstract nicety; it directly governs how algorithms are designed for real constrained hardware. Streaming algorithms, which process massive data sets (network traffic, log files, sensor streams) using memory far smaller than the stream length, are precisely $o(n)$-space algorithms in this formal sense — the read-only "input tape" is the incoming stream that cannot be stored, and the work tape is the small sketch or counter maintained in RAM. Embedded and IoT systems, with kilobytes of RAM but the need to process much larger inputs (firmware images, sensor logs), rely on the same discipline of bounding reusable memory independent of input size. Inside compilers and static analyzers, algorithms for graph reachability and dataflow analysis are often designed with an eye toward $\mathrm{NL}$-style logarithmic-space bounds, since these translate to extremely memory-efficient implementations even on graphs with millions of nodes. The theoretical class $\mathrm{PSPACE}$ captures the resource needs of solving fully quantified boolean formulas and many two-player games (generalized versions of games like Hex or Go), explaining why optimal game-tree search for such games is believed to require polynomial space but not polynomial time. Database query optimizers and model checkers used in hardware verification both operate under explicit space budgets that trace back to exactly this model: a large, read-only representation of state or schema, and a small, actively-managed work area — the same read-only-input, read-write-work-tape split introduced here. Understanding this split is the prerequisite for the next layer of the theory: L and NL as the logarithmic-space classes, Savitch's Theorem connecting deterministic and nondeterministic space, and PSPACE together with the Space Hierarchy Theorem that shows space, like time, forms a strict, infinite hierarchy of computational power.

Ask the tutor: How does Savitch's Theorem use the configuration-counting idea from this article to simulate nondeterministic space deterministically with only a quadratic blowup?