My algorithm textbook has a theorem that says
'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.'
However, it does not provide proof.
Of course I know exponential grows faster than polynomial in most cases, but is it true for all case?
What if the polynomial function is something like $n^{100^{100}}$ and exponential is $2^n$? Will the latter outgrow the former at some point?
Best Answer
Yes, it is true for all cases. This can be seen by noting that
$$\lim_{n\to\infty} \frac{n^k}{e^n} = 0$$
for any $k$. This can be seen by an application of L'Hospital's rule a number of times, or by using induction as here.