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.

  • 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.2012-09-14
  • 0
    @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.2012-09-15
  • 0
    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_).2012-09-15
  • 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
    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.2012-09-15
  • 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)$.

  • 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} $.2012-09-15
  • 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.