<p>There is a well-known theorem that states that a function <span class="math-container">$f$</span> is time constructible if and only if <span class="math-container">$f$</span> can be computed in time <span class="math-container">$O(f)$</span>. But this theorem comes with some conditions: <span class="math-container">$f$</span> must be a function where <span class="math-container">$\exists \epsilon &gt; 0$</span> such that <span class="math-container">$\forall^{\infty} n$</span> <span class="math-container">$f(n) \geq (1 + \epsilon) n$</span>.</p>
<p>What is the meaning/necessity of this additive epsilon term in the definition of <span class="math-container">$f$</span>? I can't seem to find an adequate definition of why we need it here, but not for the corresponding space constructibility theorem. My intuition is that we need a little extra time to set up and run the Turing machine, so we can't 'count' exactly <span class="math-container">$f(n)$</span> time but rather a little more.</p>
<p>As a follow-up, does this mean that <span class="math-container">$f(n) = n$</span> is not a time constructible function? Because I was under the impression that all natural polynomial functions including linear were time constructible.</p>
<p>(My model of computation is a multitape Turing machine.)</p>

CC BY-SA 4.0
2023-09-10T06:23:07.630Z
$f(n)=n$ is time constructible all right. But the proof of the theorem presumably only works for $f(n)\ge(1+\epsilon)n$. I suppose that it is not true in general that a function computable in time $O(n)$ is computable in time $n$, which sounds like something you would in the proof (but I have not looked at it). In any case, you are misinterpreting the situation: if the theorem requires further conditions, it means these conditions are *not* part of the *definition* of time-constructible functions.
Emil Jeřábek
CC BY-SA 4.0
2023-09-14T10:43:46.353Z
Welcome to TCS-SE! Please, complement your question with clear references. Statements like "There is a well-known theorem" should rather be explicit references to XXX proved the theorem YYY in year ZZZZ [Reference].
J.y B.y
<computability><time-complexity><turing-machines><time-hierarchy>
What is the meaning of the additive epsilon term in the definition of a time constructible function?
user70015
# What is the meaning of the additive epsilon term in the definition of a time constructible function?

(Asked by: username_0 on 2023-09-09)

There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a function where $\exists \epsilon > 0$ such that $\forall^{\infty} n$ $f(n) \geq (1 + \epsilon) n$.

What is the meaning/necessity of this additive epsilon term in the definition of $f$? I can't seem to find an adequate definition of why we need it here, but not for the corresponding space constructibility theorem. My intuition is that we need a little extra time to set up and run the Turing machine, so we can't 'count' exactly $f(n)$ time but rather a little more.

As a follow-up, does this mean that $f(n) = n$ is not a time constructible function? Because I was under the impression that all natural polynomial functions including linear were time constructible.

(My model of computation is a multitape Turing machine.)

**Tags:** computability, time-complexity, turing-machines, time-hierarchy
> **Comments:**
> **username_1**: $f(n)=n$ is time constructible all right. But the proof of the theorem presumably only works for $f(n)\ge(1+\epsilon)n$. I suppose that it is not true in general that a function computable in time $O(n)$ is computable in time $n$, which sounds like something you would in the proof (but I have not looked at it). In any case, you are misinterpreting the situation: if the theorem requires further conditions, it means these conditions are *not* part of the *definition* of time-constructible functions.  
> **username_2**: Welcome to TCS-SE! Please, complement your question with clear references. Statements like "There is a well-known theorem" should rather be explicit references to XXX proved the theorem YYY in year ZZZZ [Reference].  

---

## 0 answers

