Is it true that $2^n$ is $O(n!)$?

Question

I had a similar problem to this saying:

Is it true that $n!$ is $O(2^n)$?

I got that to be false because if we look at the dominant power of $n!$ it results in $n^n$. So because the base numbers are not the same it is false.

Is it true that $2^n$ is $O(n!)$?

So likewise with the bases, this question should result in false, however it is true. Why? Is the approach I am taking to solve these questions wrong?

Answer 1

Note that big-O only denotes an upper bound. So anything that grows at the same or lesser rate of $n!$ is $O(n!)$.

Answer 2

If $f(n)$ is $O(g(n))$, then there is a constant $C$ such that $f(n) \leq C g(n)$ eventually.

It turns out that $2^n$ is $O(n!)$. Can you find a constant $C$ and prove the inequality? Hint: Choose $C=2$ and try to prove $2^n \leq 2 n!$.

Answer 3

$2^n = 2 \cdot 2 \cdots 2 \le 2 \cdot 2 \cdot 3 \cdots n = 2 \cdot (n!)$ for $n\ge 2$.

Answer 4

There's already another anwer to this effect, but perhaps this example gives some much-needed intuition:

What are the values of the following, for $n=10$?

$2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\\ 1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10$

See why?

Answer 5

The criterion "base numbers are different" is not valid. The functions $2^n$ and $3^n$ have different bases, yet $2^n$ is $O(3^n)$. On the other hand, $3^n$ is not $O(2^n)$.

If we have fixed constants $m > k > 1$, then $k^n$ as a function of $n$ is $O(m^n)$.

Notice also that $n^n$ is an exponential with a larger base than $2^n$ whenever $n > 2$, and in general the order $O(f(n))$ of a function $f(n)$ is concerned with what happens as $n$ gets large. How "large" does $n$ have to be in order to ensure that $n > 2$?

Taking the original function in question, $n!$, again we have $2^n$ is $O(n!)$ for much the same reasons. Once $n \geq 4$, the ratio $\frac{n!}{2^n}$ grows by a factor of $2$ (or more) each time $n$ increases by adding $1$.

Answer 6

Another approach:

Consider: $$\sum_{n=1}^{\infty}\frac{2^n}{n!}\tag{1}$$

We have that $\limsup_{n\rightarrow \infty}\sqrt[n]{\frac{2^n}{n!}}=\limsup_{n\rightarrow \infty}\frac{2}{\sqrt[n]{n!}}=0$

Because

$$lim_{n\rightarrow \infty}\sqrt[n]{n!}=lim_{n\rightarrow \infty}(n\cdot (n-1)\cdot (n-2)\dots2\cdot 1)^{\frac{1}{n}}\geq lim_{n\rightarrow \infty} (\frac{n}{2}\cdot \frac{n}{2}\dots \frac{n}{2})^{\frac{1}{n}}\geq lim_{n\rightarrow \infty}(\frac{n}{2})^{\lfloor \frac{n}{2}\rfloor\cdot \frac{1}{n}}=\infty$$

Hence the series in (1) is convergent by the root test. So $\frac{2^n}{n!}$ is a zero-sequence from which the statement follows.

Note that you can replace $2$ by any other number.

Answer 7

Yes it is true.

$$2\le2$$ $$2\cdot2\le2\cdot 3$$ $$2\cdot2\cdot2\le2\cdot 3\cdot 4$$ $$2\cdot2\cdot2\cdot2\le2\cdot 3\cdot 4\cdot 5$$

$$\cdots$$ $$2\cdot2\cdot2\cdot2\cdots2\le2\cdot 3\cdot 4\cdot 5\cdots\cdot n$$