# 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.

-
i've checked 0, 0! <= M * 1 this holds – Supernatural Apr 22 '13 at 2:41
since M could be anything I chose shouldn't this always hold? – Supernatural Apr 22 '13 at 2:41
$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
thanks! get it now – Supernatural Apr 22 '13 at 2:46