# Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

Time hierarchy theorem states that $DTIME\bigg(o\Big(\frac{f(n)}{\log n}\Big)\bigg)\subsetneq DTIME\big(f(n)\big)$.

However space hierarchy theorem is stricter in that point since it states $SPACE\big(o(f(n))\big)\subsetneq SPACE(f(n))$. Is the same result suspected for deterministic time hierarchy?

I think I can show that $DTIME\big(o(f(n))\big)\subsetneq DTIME(f(n))$ if $f(n)\in O(n)$ but what about other functions?

• Nothing is mentioned in this survey. Aug 24, 2017 at 9:44
• If $f(n) = BB(n^2)$ and $g(n) = BB(n)$ (where $BB$ is the busy beaver function), then $g(n) = o(f(n) / \log n)$ but $DTIME(g(n)) = DTIME(f(n)) = R$. Usually, one adds some kind of constructability assumption to the time bounds to avoid these corner cases. The time hierarchy theorems assumes time-constructability. Nov 6, 2018 at 0:51
• @YonatanN, $DTIME(g(n))\subsetneq DTIME(f(n)) \subsetneq R$ (or can I compute $BB(n^2)$ in $O(BB(n))$ time?). I don't know why do you equate a fraction of recursive functions with the class of all of them. Nov 6, 2018 at 6:14
• The Busy Beaver function $BB(n)$ diagonalizes over all Turing machine to ensure that it a grows faster (in an asymptotic sense) than every computable function. One way to compute a function $f:\mathbb{N} \rightarrow \mathbb{N}$ may be to simulate a Turing machine $M$ that on input $x$ halts after $f(x)$ steps, and count the number of steps that $M$ takes until it halts. Thus, $BB$ grows faster than every possible tight running time upper bound. Consequently, every recursive function is in $\mathrm{DTIME}(BB(n))$. The time hierarchy doesn't work here because you can't simulate $BB(n)$ steps. Nov 6, 2018 at 8:42