# Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$).

Why do we have these conditions?

• Presumably the proof doesn't work without these conditions, and perhaps the result itself isn't true. – Yuval Filmus May 26 '16 at 12:33
• when we set the condition: being fully space( time) constructible, we dont need to the condition being greater than log(n), because i think all fully space constructible functions are greater than log(n). Am i right? – Yuval May 26 '16 at 12:43
• Constant functions are also fully space constructible. There are other examples which are not constant. – Yuval Filmus May 26 '16 at 13:08
• hmm, you're right, so why is there? exept these two hierarchy theorem in other theorems exist these condition! i'm interested in that. whenever we want to say a theorem about space (time) we set the condition being greater than log(n) (n)! – Yuval May 26 '16 at 13:14

And to do that, one needs to know when to finish (on each input) in case of time hierarchy, or where to prohibit the crossing (on each input) in case of space hirachy. This is possible only when the bigger bound is constructible. For time, constructibility at least requires $$\geq n$$. For space, constructibility at least requires $$\geq log(n)$$.
For full constructibility, it is not necessary to require any thing. But note that while constant functions are fully constructible (in time and space), functions in between like $$log log(n)$$, $$log log log(n)$$ (for space), $$\sqrt{(n)}$$, $$n^{2/3}$$ (for time) are not so. Informally, the spectrum of full constructibility is not continuous.