<p>For all <span class="math-container">$a≥0$</span> and <span class="math-container">$ε&gt;0$</span>, <span class="math-container">$\mathrm{DTIME}(O(n \log^{a} n))$</span> is strictly contained in <span class="math-container">$\mathrm{DTIME}(O(n \log^{a+ε} n))$</span>; see my answer <a href="https://cstheory.stackexchange.com/questions/5297/justification-of-log-f-in-dtime-hierarchy-theorem/39062#39062">here</a>.</p>

<p>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 <span class="math-container">$\log^{ε} \mathrm{time}$</span> multiplicative precision for well-behaved (time-constructible and in a certain sense continuous) time bounds.</p>

<p>A constructive proof of the strict inclusion of <span class="math-container">$\mathrm{DTIME}(O(n))$</span> in <span class="math-container">$\mathrm{DTIME}(O(n \log n))$</span> remains (to my knowledge) an open problem.</p>

CC BY-SA 4.0
2018-09-29T17:22:49.710Z
I've checked out your answer and it's nice. But could you elaborate a little bit more about how to use the padding argument?
YuiTo Cheng
CC BY-SA 4.0
2018-09-29T17:29:28.310Z
Also, where does the proof require that f is well-behaved in your sense?
YuiTo Cheng
CC BY-SA 4.0
2018-09-29T18:58:07.910Z
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
CC BY-SA 4.0
2018-09-29T16:52:24.553Z
2018-09-29T16:52:24.553Z
Dmytro Taranovsky
<p>The time hierarchy theorem implies TIME(<span class="math-container">$n$</span>) is strictly contained in TIME(<span class="math-container">$n\log^{1+ε}n$</span>) for all ε>0. Is the relationship between TIME(<span class="math-container">$n$</span>) and TIME(<span class="math-container">$nlogn$</span>) known?</p>

CC BY-SA 4.0
2018-09-29T06:09:54.313Z
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
CC BY-SA 4.0
2018-09-29T06:25:10.003Z
of course, my model of computation is multi-tape Turing machine.
YuiTo Cheng
<cc.complexity-theory><time-complexity>
TIME(n) versus TIME(nlogn)
YuiTo Cheng
# TIME(n) versus TIME(nlogn)

(Asked by: username_0 on 2018-09-29)

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?

**Tags:** cc.complexity-theory, time-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: of course, my model of computation is multi-tape Turing machine.  

---

## 1 answers

### Answer by username_2 on 2018-09-29. Score: 5 | Accepted answer

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](https://cstheory.stackexchange.com/questions/5297/justification-of-log-f-in-dtime-hierarchy-theorem/39062#39062).

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.

> **Comments:**
> **username_0**: I've checked out your answer and it's nice. But could you elaborate a little bit more about how to use the padding argument?  
> **username_0**: Also, where does the proof require that f is well-behaved in your sense?  
> **username_2**: 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)$.  

---

