1
$\begingroup$

I know this is a stupid question but I will ask it anyway. I need to do complexity analysis for n! to prove that it is not a certain complexity order. How can I go about doing that?

Problem: Prove that $n!$ is not O($2^n$).

I'm not sure how I can start this problem. I want to say that I could compare the factorial to the complexity order in an inequality. This confuses me because they are basically two different values.

  • 1
    For instance, the simplest form of Taylor's Theorem essentially says that $f(x+h) = f(x)+hf'(x)+O(h^2)$ as $h\rightarrow 0$, and this has nothing to do with computational complexity at all.2012-09-15

3 Answers 3

3

If $n!$ were $O(2^n)$, there would be positive constants $n_0$ and $C$ such that $n!\le C\cdot2^n$ for all $n\ge n_0$ or, equivalently, such that $\dfrac{n!}{2^n}\le C$ for all $n\ge n_0$. One way to show that this is not the case is to show that the fraction $\dfrac{n!}{2^n}$ can be made as large as we like by taking $n$ big enough. In other words, it would be sufficient to show that $\lim_{n\to\infty}\frac{n!}{2^n}=\infty\;.$

Notice that $\frac{n!}{2^n}=\frac{n}2\cdot\frac{n-1}2\cdot\frac{n-3}2\cdot\ldots\cdot\frac22\cdot\frac12\;;$ how does the value of this expression change when you replace $n$ by $n+1$ throughout?

  • 0
    @Michael: No, when you increase $n$ by $1$, you multiply the expression by $\frac{n+1}2$: $\frac{(n+1)!}{2^{n+1}}=\frac{n+1}2\cdot\frac{n!}{2^n}\;.$ That makes the ratio of the factorial to the exponential increase very rapidly indeed as soon as $n$ is even moderately large.2012-09-15
0

As Brian says, what you want to show is that $\displaystyle\frac{n!}{2^n}$ can't be bounded as $n\rightarrow\infty$. Now, suppose $n\geq 4$: then using Brian's breakdown, we get $\displaystyle\frac{n!}{2^n} = \frac{n}{2}\cdot\frac{n-1}{2}\cdot\ldots\cdot\frac{3}{2}\cdot\frac{2}{2}\cdot\frac{1}{2}$. But all the terms between $\displaystyle\frac{n-1}{2}$ and $\displaystyle\frac{2}{2}$ are at least $1$, so we know that (at the very least) $\displaystyle\frac{n!}{2^n}\geq\frac{n}{2}\cdot 1\cdot\ldots\cdot 1\cdot\frac{1}{2} = \frac{n}{4}$ for all $n\geq 4$. Since this expression obviously isn't bounded, then neither is $n!/2^n$, and so we know that it can't be the case that $n!=O(2^n)$.

  • 0
    @Henry Good point - I was focusing on having every term \gt 1, but that's hardly necessary. I'll tweak my argument a bit.2012-09-15
0

To modify Steven Stadnicki's proof moderately, since all the numbers from $n/2$ to $n$ are at least $n/2$ and there are at least $n/2$ of them, $n! \ge (n/2)^{n/2} = \frac{n^{n/2}}{2^{n/2}} $ so $\frac{n!}{2^n} \ge \frac{n^{n/2}}{2^{3n/2}} = (n/2^3)^{n/2} = (n/8)^{n/2} $. If $n > 8m$, $\frac{n!}{2^n}> m^{4m}$, so by choosing $m$ (and therefore $n$) large enough, we can make $\frac{n!}{2^n}$ as large as we want.

To show that $n!/k^n$ gets arbitrarily large, for any real $k > 1$, look at the $n/k$ values from $n(1-1/k)$ to $n$. Then $n! >(n(1-1/k))^{n/k}$, so, letting $c = 1-1/k$, $n!/k^n >\frac{(cn)^{n/k}}{k^n} = \big(\frac{(cn)^{1/k}}{k}\big)^n = \big(\frac{cn}{k^k}\big)^{n/k} = (r n)^{n/k} $ where $r = c/(k^k) = (1-1/k)/(k^k)$ .

Again, by making n$ large, this can be made arbitrarily large.