Definition. Runtime [runtime]

Complexity theory.

1. The runtime of a Turing machine $M$ is $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$: $f(n) = \max\left( {x \in \Sigma \ast ,|x| = n} \right)$. (the number of steps of $M$ on input $n$ until it halts) (assume $M$ is a decider for simplicity)
2. The runtime of a nondeterministic Turing machine $\text{NTM}$ on input $X$ is max-length of any root-leaf path. For deciders – no infinite paths!