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 are the functions ${\mathrm{Time}}_M(n):={\max }_{\mathrm{\mid }w\mathrm{\mid }=n}{\mathrm{time}}_M(w),{\mathrm{Space}}_M(n):={\max }_{\mathrm{\mid }w\mathrm{\mid }=n}{\mathrm{space}}_M(w)\mathrm{.}$

For a nondeterministic machine $N$, define ${\mathrm{time}}_N(w)$ and ${\mathrm{space}}_N(w)$ as the maximum over all halting branches on input $w$, provided every branch halts. The worst-case functions ${\mathrm{Time}}_N$ and ${\mathrm{Space}}_N$ are then defined by the same maxima over inputs 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.