Im have trouble with this question.

Question

im having a bit of trouble with this problem and and how to go about it.

show that: 2^n=O(n!)

thanks

Answer 1

We can "cheat" on this problem by showing the stronger result $2^n < n!$ for $n \geq 4$.

Base case: When $n=4$ we have $2^4=$ [[fill in the blank]] $<4!$.

Inductive step: If $2^n < n!$ then $2^{n+1}=$ [[fill in the blank]] $<(n+1)!$.

We conclude that $2^n<n!$ for all $n \geq 4$. Hence $2^n=O(n!)$.

Answer 2

The definition says that $f = O(g)$ if and only if there is a value $x_0$ and a value $M$ such that $|f(x)| \leq M|g(x)|$ for all $x \geq x_0$. Prove that for $n >3$ this is the case.