# What is the correct way to define time constructible functions?

Sipser defines a time constructible function as

$f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $f(n)$ in binary to the output tape in $O(f(n))$ time.

whereas Sanjeev Arora and Barak defines it as

$f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $1^{f(n)}$ in binary to the output tape in $O(f(n))$ time.

I am unable to see how are these two definitions equivalent. Isn't there a case where writing value in binary takes less time that writing it in unary ? Also what is the reason for inputs being given in unary rather than binary or some other base $k > 2$ ?

The two definitions are probably equivalent (perhaps $f(n)$ need be not too small): given $f(n)$ in binary you can write $1^{f(n)}$ in $O(f(n))$ time, and vice versa. The ideas are as follows.
Binary to unary: Inductively construct $1^{b_m b_{m-1} \ldots b_{m-t}}$, where $b_m\ldots b_0$ is the binary representation of $1^{f(n)}$. At each step we need to roughly double the string of 1s, and in stage $t$ this takes roughly $O(f(n)/2^{m-t})$ time. Taking into account all stages, we get roughly $O(f(n))$.
Unary to binary: Construct the binary representation of $f(n)$ from LSB to MSB by repeatedly dividing $f(n)$ by two. The $t$th division by two requires time $O(f(n)/2^t)$, so overall this runs in time roughly $O(f(n))$.
As to why the input is in unary rather than in binary, this ionly affects small $f(n)$; as we have seen, converting between $1^n$ and $n$ should take time $O(n)$, and this is affordable as long as $f(n) = \Omega(n)$.
• It might, but you'll have to check the details to make sure. Also, for small $n$ it might take too much time to read the input. Feb 16, 2016 at 12:39