Dominating Big-O

Question

How could I prove that $O(5^n)$ is dominated by $O(n!)$ by using induction?

Or: $5^n \in O(n!)$

I've got the basic formulas written out in regards to $f(k+1)$ but I'm just not sure how to proceed.

score 1 · Answer 1 · answered Oct 04 '17 at 13:51

1

Hint:

Set $u_n=\dfrac{5^n}{n!}$ and use the ratio test to show that $5^n=o(n!)$. A fortiori, $5^n=O(n!)$.

answered Oct 04 '17 at 13:51

Bernard

175,478

How would you approach the problem if you were to use induction to prove it though? – Oct 04 '17 at 14:16
Induction on what? $n$ is not a parameter in such a question, it is the variable of two functions. You can use some form of induction when applying the ratio test, or to find the constant for the domination relation explicitly – Bernard Oct 04 '17 at 14:21

score 1 · Answer 2 · answered Oct 04 '17 at 14:19

There is no need to use induction here. Just notice that for $n \geq 5$ all but we have that all but the first $4$ factors in $n!$ are at least $5$. Therefore $n! > 4! \cdot 5^{n-4} = \frac{24}{5^4} \cdot 5^n$. So there is an $n_0$ and a $c$ such that $5^n \leq n!$ whenever $n \geq n_0$.

Dominating Big-O

2 Answers2