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

Question

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.

Answer 1

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.

Answer 2

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