Prove the following statements:
$2^n$ is $O(n!)$, and
$n!$ is not $O(2^n)$
not sure where to start with these two... thanks
Asked
Active
Viewed 50 times
0
-
Do you mean $n!$ is not $O(2^n)$? – vadim123 Apr 22 '13 at 02:27
-
ops, yes thanks – Supernatural Apr 22 '13 at 02:30
1 Answers
2
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$.
Suppose that there is an $M$ such that $|n!| \le M |2^n|$ for all $n$ (sufficiently large). Try to find a contradiction.
vadim123
- 82,796
-
-
-
1$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 02:43