# What is the meaning of the additive epsilon term in the definition of a time constructible function?

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.)

• $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. Sep 10 at 6:23
• 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]. Sep 14 at 10:43