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 Feb 5 '19 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 Feb 5 '19 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 Feb 5 '19 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.