# Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) Turing machine that for $n$ given, halts after exactly $f(n)$ steps, and just asked if we could now prove that $n!$ is fully time constructible (and moved on).

I am not sure how the proof goes, but I am thinking it has to use $n^k$ time constructability to some extent, or some identity involving factorials, since we showed $n^k$ is (fully) time constructible using $n^k = n + \sum_{i=1}^{i=k-1}(n - 1)n^i$.

Hints would be appreciated too, really. Thanks in advance.

Let us assume we have find $n!$ on input $n$. Our complexity is terms of length of the input ( we assume it to be $L=O(logn)$ ). Multiplication of a $k$ bit by $l$ bit number via standard multiplication takes $O(kl)$ operations ( also after multiplication number of bits in the resultant if $O(k+l)$ ) . We multiply linearly in a loop from $1$ to $n$ to get $n!$. So number of operations carried out are upper bounded by $\# = L^2 ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Thus it is space and time constructible.
• @coptus According to Wikipedia it seems like there are 2 different definitions for time-constructible function. One only requires the function to halt after exactly $f(n)$ steps, while the other requires halting in $O(f(n))$ steps but also requires the output to be the binary representation of $f(n)$. It seems to me like sashas proved according to the second definition Oct 20 '18 at 17:12