5
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Yes. Exponential of base $> 1$ will eventually grow faster than any polynomial. $\endgroup$
    – Tunococ
    Sep 20, 2013 at 9:20
  • 1
    $\begingroup$ 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$... $\endgroup$
    – user856
    Sep 20, 2013 at 9:38
  • $\begingroup$ 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)$. $\endgroup$ Sep 20, 2013 at 9:52

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ I don't understand... $\endgroup$ Mar 12, 2018 at 17:36
  • 1
    $\begingroup$ @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$. $\endgroup$
    – user21820
    Mar 14, 2018 at 11:55
  • $\begingroup$ @Niing: If you still do not get it, specify exactly which part of my comment you cannot understand, and I will explain. $\endgroup$
    – user21820
    Mar 14, 2018 at 11:56
  • $\begingroup$ 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... $\endgroup$ Mar 14, 2018 at 16:12
  • $\begingroup$ @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. =) $\endgroup$
    – user21820
    Mar 14, 2018 at 16:53
1
$\begingroup$

Hint: Yes. See Taylor expansion of exponential function.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .