Is it true that $2^n$ is $O(n!)$? 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?
 A: $2^n = 2 \cdot 2 \cdots 2 \le 2 \cdot 2  \cdot 3 \cdots  n = 2 \cdot (n!)$ for $n\ge 2$.
A: 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!$.
A: 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.
A: Note that big-O only denotes an upper bound. So anything that grows at the same or lesser rate of $n!$ is $O(n!)$.
A: 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$$
A: 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?
A: 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$.
