# prove the statement (big O notation)

Prove the following statements:

1. $2^n$ is $O(n!)$, and

2. $n!$ is not $O(2^n)$

-
Do you mean $n!$ is not $O(2^n)$? –  vadim123 Apr 22 '13 at 2:27
ops, yes thanks –  Supernatural Apr 22 '13 at 2:30

1. Note that $\frac{2^n}{n!}=\frac{2\times 2 \times 2\cdots \times 2}{1\times 2 \times 3\times 4\cdots \times n} \le 2$ for all $n$. Hence $|2^n| \le 2 |n!|$ for all $n$.
2. Suppose that there is an $M$ such that $|n!| \le M |2^n|$ for all $n$ (sufficiently large). Try to find a contradiction.
$M$ needs to be chosen, held fixed. It needs to work for all $n$ (except possibly finitely many small ones). –  vadim123 Apr 22 '13 at 2:43