1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.