Space complexity

Definition

Let $\Sigma$ be a finite alphabet. Consider a multitape Turing machine $M$ with a read-only input tape and one or more read-write work tapes. Suppose that $M$ is deterministic and halts on every input. Let $w \in \Sigma^*$ be an input. The space used by $M$ on $w$ is the number of distinct work-tape cells that the heads of $M$ visit while $M$ runs on $w$. The space complexity of $M$ is the function $s_M \colon \N \to \N$ with $$s_M(n) = \max \set{\text{space used by } M \text{ on } w : w \in \Sigma^*, \ \abs{w} = n}.$$ For a nondeterministic Turing machine that halts on every branch, the maximum is also taken over all computation branches. For a function $f \colon \N \to \N$, $\mathrm{DSPACE}(f)$ is the set of languages $L \subseteq \Sigma^*$ decided by some deterministic machine $M$ with $s_M(n) = O(f(n))$, in big O notation. The class $\mathrm{NSPACE}(f)$ is defined in the same way with nondeterministic machines.