I am reading Sipser's Introduction to the Theory of Computation, and encountered two propositions:

  1. $A = \{0^k1^k \mid k ≥ 0\}$ is nonregular language (pumping lemma).
  2. Any language that can be decided in $o(n\log n)$ time on a single-tape Turing machine is regular.

The author shows how to construct a Turing machine that recognizes $A$ in $O(n\log n)$ time. Meaning, nonregular language was recognized in $o(n\log n)$.

Can you please explain where is my mistake in understanding?

This topic describes similar question but does not explain why $A$ was accepted in $O(n\log n)$ time.


2 Answers 2


You misunderstood $O$ vs $o$. Specifically, for every function $f(n)$ it holds that $f(n)\in O(f(n))$, but $f(n)\notin o(f(n))$ (because $\lim_{n\to \infty} \frac{f(n)}{f(n)}=1\neq 0$).

There is indeed a theorem showing that a language that is decidable in $o(n\log n)$ time is regular, and the example above shows that there are decidable languages in $O(n \log n)$ time that are not regular.


Here is a similar example.

Claim: If a language is recognized by a Turing machine running in $o(n)$, then it is accepted by a Turing machine running in $O(1)$.

For the proof, find $n_0$ such that on inputs of size $n_0$, the Turing machine $M$ terminates in time less than $n_0$. For every input $x$ of length $n_0$, the behavior of $M$ on $x$ is the same as its behavior on $xy$ for any string $y$, because $M$ doesn't run long enough to notice the difference. If we denote the running time of $M$ on inputs of length $n$ by $T(n)$, this shows that its running time is at most $\max_{n \leq n_0} T(n)$, which is constant.

Claim: The language of all binary strings of even parity is recognized by a Turing machine running in time $O(n)$, but not by any Turing machine running in $O(1)$.

You can simulate a DFA to accept this language in time $n$. On the other hand, a machine running in time $T$ doesn't reach the last bit of inputs whose length is larger than $T$. Since the last bit determines whether the machine should accept an input or not, such a machine cannot accept this language.

The two claims do not contradict each other, since a machine running in $O(n)$ doesn't necessarily run also in $o(n)$.


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.