Which of the following identities are true? Justify your answer - n! = O(4^n)..

Question

Which of the following identities are true? Justify your answer

a)$n! = O(4^n)$

b)$4^n = O(n!)$

If I let $n = 0$ then $(0)! = O(4^0) \implies 1 = O(1)$ so this is true I think?

$4^n = O(n!)$

In that case, wouldn't this be true as well?

Answer 1

You need to go back to the definition of big O. Let $f$, $g$ be functions of $x$. Then $f = O(g)$ if and only if there exists some number $M$ such that $\left|f\right| \le M\left|g\right|$. In other words, if you can find a constant $M$ such that$$\left|f\right| \le M \times \text{some other function},$$then $f$ is $O(g)$.

Here is an example. Let $f = 6x^4 - x^2 + 5$. Then$$\left|6x^4 - x^2 + 5\right| \le \left|6x^4 + x^2 + 5\right| \le \left|6x^4 + x^4 + 5x^4\right| = 12\left|x^4\right|.$$That is why we would say $f = O(x^4)$, since there exists a constant, namely $12$, that fits our definition of big O. In your case, you need to figure out which equation is larger, or rather, which graph produces an upper bound for the other – to that extent, this graph should help. Anyways, the reason big O is useful is because it provides a function $f$ with an upper bound (worst case) of another function. In our example above, the worst case was $x^4$, hence why $f$ was big O of $x^4$.