prove the statement (big O notation)

Question

Prove the following statements:

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

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

not sure where to start with these two... thanks

Answer 1

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.