Worst-case time and space complexity of a machine

Let $M$ be a deterministic $k$-tape Turing machine. For an input word $w$, let ${\mathrm{time}}_M(w)$ be the number of steps in the computation of $M$ on $w$ when that computation halts, and let ${\mathrm{space}}_M(w)$ be the total number of tape cells that are ever visited during that computation across all $k$ tapes.

If $M$ halts on every input of length $n$, its worst-case time complexity and worst-case space complexity at that length are ${\mathrm{Time}}_M(n):=\max (\{0\}\cup \{{\mathrm{time}}_M(w):\mathrm{\mid }w\mathrm{\mid }=n\}),{\mathrm{Space}}_M(n):=\max (\{0\}\cup \{{\mathrm{space}}_M(w):\mathrm{\mid }w\mathrm{\mid }=n\})\mathrm{.}$ Thus both values are $0$ when the input alphabet has no words of length $n$.

For a nondeterministic machine $N$, a maximal branch either is infinite, ends in an accepting or rejecting state, or ends at a nonhalting configuration with no allowed transition. Suppose that every maximal branch on $w$ ends in an accepting or rejecting state. Since the computation tree is finitely branching, it then has finitely many nodes: if it had arbitrarily large depth, repeatedly taking the first child with descendants at arbitrarily large depths would produce an infinite branch. Define ${\mathrm{time}}_N(w)$ and ${\mathrm{space}}_N(w)$ as the maxima over these finitely many halting branches. The worst-case values ${\mathrm{Time}}_N(n)$ and ${\mathrm{Space}}_N(n)$ use the same input maxima with $0$ adjoined as above, provided the branch condition holds for every input of length $n$.

We say that a machine runs in time at most $t(n)$ when its worst-case time is bounded by $t$, and runs in space at most $s(n)$ when its worst-case space is bounded by $s$.

• The time and space functions are attached to machines that halt on all inputs under consideration, which is the regime needed for complexity classes.

• Space counts visited cells, not merely cells that happen to be nonblank in the initial input configuration.