# TIME(n) versus TIME(nlogn)

The time hierarchy theorem implies TIME($$n$$) is strictly contained in TIME($$n\log^{1+ε}n$$) for all ε>0. Is the relationship between TIME($$n$$) and TIME($$nlogn$$) known?

• On a single tape machine, the non-regular language $\{A^nB^n | n \geq 0\}$ is easily decidable in TIME[$O(n \log n)$], but all languages decidable in TIME[$o(n \log n)$] are regular. This same argument does not work for multi-tape machines. – Yonatan N Sep 29 '18 at 6:09
• of course, my model of computation is multi-tape Turing machine. – YuiTo Cheng Sep 29 '18 at 6:25

For all $$a≥0$$ and $$ε>0$$, $$\mathrm{DTIME}(O(n \log^{a} n))$$ is strictly contained in $$\mathrm{DTIME}(O(n \log^{a+ε} n))$$; see my answer here.
To recap, the logarithmic overhead comes from tape reduction (and is not needed if the number of tapes is fixed and is at least two). There is a nonconstructive argument that converts the logarithmic overhead into time hierarchy at $$\log^{ε} \mathrm{time}$$ multiplicative precision for well-behaved (time-constructible and in a certain sense continuous) time bounds.
A constructive proof of the strict inclusion of $$\mathrm{DTIME}(O(n))$$ in $$\mathrm{DTIME}(O(n \log n))$$ remains (to my knowledge) an open problem.
• For time-constructible $f(n) > n$, if $\mathrm{Time}(O(f(n))) = \mathrm{Time}(O(n))$, then by padding input to length $f(n)$, $\mathrm{Time}(O(f(f(n)))) = \mathrm{Time}(O(f(n)))$ (and similarly with appropriate $g(n)$ in place of $n$). The 'continuity' of a function $g$ is used to get from $g$ to $>g \log g$ using a finite composition of $f$ with $f(g(n)) < g(n) \log^ε g(n)$. – Dmytro Taranovsky Sep 29 '18 at 18:58