# Why there is $\log n$ factor in time constructible definition?

I saw two different definitions of time constructible functions.

In Sipser (third edt), Definition 9.8, defines $$t(n)$$ is time constructible if $$t(n)\geq O(n \log n)$$ and maps $$1^n$$ to the binary representation of $$t(n)$$ in time $$O(t(n))$$.

In arora, there is a lower bound $$t(n) \geq n$$ instead of $$t(n) \geq O(n \log n)$$ , so i wonder why there is factor $$\log n$$ in sipser definition ? What is wrong with $$t(n) \geq n$$ ? Is it because of single-tape multi-tape arguments ?

Is it because sipser version of time hierarchy theorem simulate a single tape TM by another single tape TM for a prespecified number of steps ?

• The version of the time hierarchy theorem in Anup Rao's notes states that $\mathsf{TIME}(r(n)) \neq \mathsf{TIME}(t(n))$ if $r,t$ are time constructible and $r\log r = o(t)$. He only requires $r(n),t(n) \geq n$, which implies that $t(n) = \omega(n\log n)$. Perhaps this is the source of the discrepancy — where the logarithmic factor comes from. Commented Aug 11, 2021 at 20:25
• @YuvalFilmus Is it because computing $n$ in binary costs $n \log n$ ? As we know incrementing counter by one cost $\log n$ ? Commented Aug 12, 2021 at 14:29
• There is logarithmic overhead in simulating a Turing machine. Commented Aug 12, 2021 at 14:35
• @YuvalFilmus I know that, but if $t(n) \geq n$ so we compute $t(n)$ in binary and we count down for each step, in sipser version of THT , shifting counters bit is the cause of overhead. (But in arora , he use Efficient TM which introduced by Hennie and Stern) But my question is we only use time constructibility to compute $t(n)$ , why $t(n)$ must be greater than $n \log n$ instead of greater than $n$ ? Commented Aug 12, 2021 at 14:41
• If $r(n) \ge n$ then $t(n) = \omega(n\log n)$. Commented Aug 12, 2021 at 14:45