# Is 'every exponential grows faster than every polynomial?' always true?

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?

• Yes. Exponential of base $> 1$ will eventually grow faster than any polynomial. Sep 20, 2013 at 9:20
• For intuition, take logs on both sides and you have $100^{100}\log n$ versus $n\log 2$. Hopefully you believe that $\log n$ grows much slower than $n$...
– user856
Sep 20, 2013 at 9:38
• The result is correct. In the very long run, $f(n)=(1.00000001)^n$ "beats" $g(n)=n^{9999999999}$. However, for all practical purposes, an "exponential" algorithm that takes time $f(n)$ on input of size $n$ may be much more practical than a "polynomial" algorithm that takes time $g(n)$. Sep 20, 2013 at 9:52

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.

Let $n = k^2$.

Then $n^c = k^{2c}$ and $2^n = (2^k)^k$.

Clearly $2^k \ge k+1 > k$ so all we need is $k > 2c$.

In general if we want to find $n \in \mathbb{N}$ such that $r^n > n^c$ where $r > 1$, we can do essentially the same:

Let $n = ak^2$ where $a > \log_r(2)$.

Then $r^n > (2^k)^k$ and $n^c = a^c k^{2c}$.

It is then enough to choose $k$ such that $k > a$ and $k > 3c$, so that $n^c < k^{3c} < (2^k)^k < 2^n$.

• I don't understand... Mar 12, 2018 at 17:36
• @Niing: My answer may have been a bit cryptic, but it should have been decipherable after some effort. Given constant $c$, to prove $2^n > n^c$ as $n \to \infty$, let $n = k^2$ and observe that $2^n = (2^k)^k > k^k$ and $n^c = k^{2c}$, and so it should be clear that the desired inequality holds because $k > 2c$ as $n \to \infty$. Similarly, given constants $c$ and $r>1$, to prove $r^n > n^c$ as $n \to \infty$, let $n = ak^2$ where $a > \log_r(2)$, so $r^n = (2^{ak})^k > (2^k)^k$ and $n^c = a^c k^{2c} < k^{3c} < (2^k)^k$ because $a < k$ and $3c < k$ as $n \to \infty$. Mar 14, 2018 at 11:55
• @Niing: If you still do not get it, specify exactly which part of my comment you cannot understand, and I will explain. Mar 14, 2018 at 11:56
• I've asked a question about how to prove what you just did... And I've read, at least for me, a lot of related posts. Your explanation is the best..., since you didn't use any advanced concept like the limit of a quotient. TLDR: thank you... Mar 14, 2018 at 16:12
• @Niing: Yes that is precisely the reason I posted my answer a year after the others, to demonstrate that we can in fact do a lot by purely elementary means. Of course, once we learn asymptotic expansion, we ought to always just use it, and in this case we can use $exp(n/c) > 1+n/c+n^2/2c^2 > n$ as $n \to \infty$. But it is good to know what we can do with simpler tools. =) Mar 14, 2018 at 16:53

Hint: Yes. See Taylor expansion of exponential function.