Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Note that you've got a bit of the same confusion here that you've had on previous questions with respect to conflating big-O notation and complexity - I strongly recommend dropping your use of the latter word entirely until you're more comfortable with the usage of the notation; I think it may be getting in the way of your understanding. –  Steven Stadnicki Sep 14 '12 at 23:38
    
@Steven Stadnicki Do you have any good resources that can help me remove my confusion on this? I must say that my algorithms teacher is not making it very clear and my discrete teacher decided to gloss over the subject as well. So bascially in the CS side of my classes, we all just put the two together so it is hard to separate. –  Michael Guantonio Sep 15 '12 at 0:18
    
Michael: While I don't have any specific, I'd suggest looking at asymptotic analysis as a potential starting point, as while that's often used in complexity theory it's hypothetically divorced from it. You might also look at numerical analysis specifically, for instance into error estimates for solving differential equations and integrals (some magic words here are Trapezoid Rule, Runge-Kutta and Simpson's Rule). –  Steven Stadnicki Sep 15 '12 at 0:31
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. –  Steven Stadnicki Sep 15 '12 at 0:32

3 Answers 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?

share|improve this answer
    
I would believe that the series would only increase by one. Since the limit itself is the node going to infinity there is really no change for n+1. n+1 will still basically be a very large number as it approaches infinity. –  Michael Guantonio Sep 15 '12 at 1:44
    
@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. –  Brian M. Scott Sep 15 '12 at 1:50

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

share|improve this answer
1  
You could simplify this slightly to $\displaystyle\frac{n!}{2^n} \ge \frac{n}{2} \times \left(\frac{2}{2}\right)^{n-2} \times \frac12 = \frac{n}{4} $. –  Henry Sep 15 '12 at 0:29
    
@Henry Good point - I was focusing on having every term \gt 1, but that's hardly necessary. I'll tweak my argument a bit. –  Steven Stadnicki Sep 15 '12 at 0:35

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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