Argument in proving that function is not polynomial time in bit length of input seems faulty

Question

I am currently solving a question that asks which of the following functions can be calculated in polynomial time:

$$n!, \binom{n}{5}, \binom{2n}{n}, n^{\lfloor \lg n \rfloor}, \lfloor \sqrt{n} \rfloor, \text{the smallest prime factor of } n, \text{the number of prime factors less than }n.$$

In proving the first one, I thought $n! \geq n$ and the input size is $\log_2 n$ so the output cannot even be written in polynomial time. So then clearly the calculation cannot be done in polynomial time.

But then I thought I must have some misunderstanding, since by that logic even just calculating $n$ from the input (that is, the identity function) should not be polynomial time. But that's clearly not possible.

What is the problem in my thinking, and instead how should I be thinking about these?

Answer 1

You should measure the length of the output in the same way you measure the length of the input.

For example, when computing the identity function $f(m) = m$, an input $m$ has input length $n = \Theta(\log m)$ and output length also $n$, which is polynomial in $n$.

The factorial function, in contrast, has much too long output length. Indeed, if the input is $n$, then by Stirling's formula, the length of the output is $\Theta(n\log n)$, which is exponential in the input length $\Theta(\log n)$.