# Regarding the definitions of time-constructible functions on Wikipedia

I am reading the Wikipedia article on time-constructible functions and got confused by its definitions, given as follows:

There are two different definitions of a time-constructible function. In the first definition, a function $$f$$ is called time-constructible if there exists a positive integer $$n_0$$ and Turing machine $$M$$ which, given a string $$1^n$$ consisting of $$n$$ ones, stops after exactly $$f(n)$$ steps for all $$n \ge n_0$$. In the second definition, a function $$f$$ is called time-constructible if there exists a Turing machine $$M$$ which, given a string $$1^n$$, outputs the binary representation of $$f(n)$$ in $$\mathcal{O}(f(n))$$ time (a unary representation may be used instead, since the two can be interconverted in $$\mathcal{O}(f(n))$$ time).1

1. If I am not mistaken the two definitions are not equivalent: The first one is more strict.
2. I think this definitions are lacking the requirement that $$f(n) \ge n$$, since the part about converting an unary to a binary representation might not be true as this requires $$f(n) \ge n$$, i.e. the algorithm needs to be able to read the input, which might not be the case for small enough $$f(n)$$.

Am I right with this or am I missing something here?

• (It was long ago, so I'm not confident) I think that you are right about 1, but it doesn't matter in applications (s.t. hierarchy theorems). 2 implies that $f(n) = o(n)$ is not time-constructible. Commented Nov 5, 2021 at 10:52