We can compute the binary representation of $n$ and similarly by decrementing the value of $n$ by $1$ each time we can get all values from $2$ to $n$. We can now use a Turing Machine that multiplies binary numbers to get the value of $n$. But will this computation be bounded by $O(n)$? That is, can $n!$ be a time constructible function?

  • $\begingroup$ Related: cs.stackexchange.com/questions/55761/… $\endgroup$
    – dkaeae
    Commented Feb 5, 2019 at 15:36
  • $\begingroup$ It might be useful to mention what definition of time constructible you are referring to (there is at least a couple) as well as whether the input $n$ is given either in unary or binary. $\endgroup$
    – dkaeae
    Commented Feb 5, 2019 at 15:37
  • $\begingroup$ $n$ is given in binary. Here time constructible would refer to producing the binary representation in $O(f(n))$ time $\endgroup$
    – kauray
    Commented Feb 5, 2019 at 15:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.