# Single-tape $o(n\log n)$ Turing machines and nonregular languages

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.

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)$$.