Time complexity

Remarks

Example: the language $\set{0^k 1^k : k \ge 0}$ is in $\mathrm{DTIME}(n)$. A two-tape machine checks that the input has the form $0^* 1^*$ and copies the $0$s to its second tape. Then it crosses off one of them for each $1$, so it uses $O(n)$ steps. On a single-tape Turing machine this language can be decided in time $O(n \log n)$ but not in time $O(n)$. In fact every language decided by a single-tape machine in time $o(n \log n)$ is regular. Non-example: a machine that does not halt on some input has no time complexity in this sense. The same definitions apply to other models, such as random-access machines, where each instruction counts as one step.