Comparing $\;2^n\;$ and $\;n!\;$
I need to rewrite one or the other so they can be more easily compared (i.e. have similar form). Because of the factorial, I'm a little lost as to how to compare the two functions. Normally, I would take the logarithm when trying to re-express a power like $2^n$, but I don't think this will work, since I don't know how to take the logarithm of a factorial, if at all.
Might the series expansions of either functions be the right approach? If not could, someone point me in the right direction?
$\endgroup$ 47 Answers
$\begingroup$$$2^n \;=\;\; \underbrace{\;2\cdot 2 \cdot 2\cdot 2\cdot\, \cdots \,\cdot 2 \; \cdot \;2\;}_{\text{n $ $factors of $2$}}$$
$$n! = \underbrace{1\cdot 2\cdot 3 \cdot 4\cdot\, \cdots\,\cdot (n - 1)\cdot n}_{\text{n factors}}$$
When we compare the products $\,$ factor-by-factor,$\,$ we can easily see that when $n \geq 4$, $\;n!\;>\;2^n$.
This can, of course, be formalized using induction on $n$.
$\endgroup$ 0 $\begingroup$Consider for $n \ge 4$: $$ 2^n = 2 \cdot 2 \cdot 2^{n - 2} < 2 \cdot 3 \cdot 4 \cdot \ldots \cdot n = n! $$
$\endgroup$ 5 $\begingroup$By induction, $(n+1)!=(n+1) \cdot n! \geq (n+1) \cdot 2^n \geq 2 \cdot 2^n=2^{n+1}$ if $n! \geq 2^n$. Therefore, because $4$ is the smallest integer such that $2^n \leq n!$ is true, you deduce that $n! \geq 2^n$ for all $n \geq 4$.
$\endgroup$ 4 $\begingroup$Note that if $n\ge 2$ then $$\frac{2^n}{n!} =\left(\frac{2}{1}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots+\frac{2}{n-1}\right)\cdot\left(\frac{2}{n}\right)=\left(\frac{2}{2}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots+\frac{2}{n-1}\right)\cdot\left(\frac{4}{n}\right).$$ The product $\frac{2}{2}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots\frac{2}{n-1}$ is $\le 1$. It follows that $$\frac{2^n}{n!}\le \frac{4}{n}$$ when $n\ge 1$, and therefore $\frac{2^n}{n!}\to 0$ as $n\to\infty$.
$\endgroup$ $\begingroup$Normally, I would take the logarithm when trying to re-express a power like 2n, but I don't think this will work, since I don't know how to take the logarithm of a factorial, if at all.
$\log(n!) = \log(1) + \log(2) + \log(3) + ... + \log(n)$
You can approximate the sum by integrating the log function from 1 to $n$. Recall that the anti-derivative of the natural log is $x \ln{x} - x + C$. From this, you get log(n!) = O(n log n). Which is larger than $\log(2^n) = O(n)$.
If you're studying sorting algorithms in computer science, this is why comparison-based sorting algorithms (e.g., quicksort or mergesort) require O(n log n) time: These algorithm can be analyzed as a binary decision tree with $n!$ leaves (the possible permutations of the array). Taking the (base-2) logarithm gives you the depth of the tree (if it's balanced), which equals the number of comparisons required.
$\endgroup$ 2 $\begingroup$\begin{align*} 2^n &= 2 \times 2 \times \dots \times 2 \times 2 \times 2 \\ n! &= 1 \times 2 \times \dots \times (n-2) \times (n-1) \times n \end{align*}
Both of these expressions are $n$ numbers multiplied together. So for $n < 4$, $2^n > n!$ because the 1 in $n!$ adds nothing. However, for $n \geq 4$, $n!$ will always be larger than $2^n$, because the 4 in $4!$ is $2 \times 2$ so it compensates for the extra 2 in $2^n$, and all other terms $3,5,6,7,\dots$ are all larger than $2$.
$\endgroup$ $\begingroup$Method 1: You can take a graphical approach to this problem:
It can be seen that the graphs meet at (0, 1), $2^x$ is greater until they intersect when $x \approx 3.459$, and then the factorial becomes much greater. Alternatively, plot $x! - 2^x$ to see a demonstration of the difference.
Method 2: use Stirling's approximation,
$$x! \sim \left(\frac{x}{e}\right)^x\sqrt{2\pi{x}}\left(1 + \frac{1}{12x}\right)$$
Now you can take logarithms of both expressions. Comparing the graphs of $y = x$ and the base 2 logarithm of the above expression, it can be seen that the latter quickly rises above the former.
$\endgroup$
