It is known that any (deterministic, single-taped) Turing-machine that runs in time $o(n\log n)$, decides a regular language (e.g., see this link). Thus, there exists an equivalent Turing-machine that runs in time $O(n)$. In other words, if $t(n)=o(n\log n)$ then $$\mathsf{DTIME}\left(t\left(n\right)\right)\backslash\mathsf{DTIME}\left(n\right)=\emptyset.$$

I was wondering whether there exists an example in which the original Turing-machine was not already running in time $O(n)$.

To sum up: Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?

  • $\begingroup$ You can make a Turing machine run in $O(n \log \log n)$ if you'd like to. However, do you need it to decide a regular language? $\endgroup$
    – Pål GD
    Jun 4, 2017 at 13:33
  • 1
    $\begingroup$ @PålGD Sure, that's trivial. Do you mean $\Theta(n\log\log n)$? And is it a single-tape machine? $\endgroup$ Jun 4, 2017 at 15:59

1 Answer 1


The answer seems to be negative, according to Corollary 4.12 of Verifying Time Complexity of Deterministic Turing Machines by David Gajser (ArXiv).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.