4
$\begingroup$

I am trying to understand how to prove that a polynomial will always grow faster than a logarithm.

$\log n = o(n^\epsilon), \epsilon>0$

Intuitively, it is obvious, and plugging in a few numbers always yields true, but how can I prove this?

Maybe this can be done inductively (I would prefer this method if someone would explain it), but I attempted to prove through the use of derivatives and L'Hôpital's rule, namely:

$\lim_{n\rightarrow\infty}\frac{\log n}{n^\epsilon} = \lim_{n\rightarrow\infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}$ = 0

Is this getting me in the right direction to prove that the upper bound of $\log n$ it is strictly less than $n^\epsilon$?

$\endgroup$
  • 5
    $\begingroup$ Simplify that fraction further. $\endgroup$ – Ryan Sep 10 '16 at 19:32
  • $\begingroup$ Intuitively, if eps = 0.001 then this isn't obvious at all. $\endgroup$ – gnasher729 Sep 10 '16 at 22:57
  • 1
    $\begingroup$ Possible duplicate of Sorting functions by asymptotic growth $\endgroup$ – David Richerby Oct 11 '16 at 13:57
2
$\begingroup$

Here is a simple proof which avoids L'Hôpital's rule.

We start with the observation $$ \log n = \int_1^n \frac{dx}{x} \leq \int_1^n dx \leq n, $$ and so $$ \frac{\log n}{n^2} \leq \frac{1}{n} \xrightarrow{n\to\infty} 0. $$

Given $\epsilon > 0$, using the fact that $\lim_{n\to\infty} n^{\epsilon/2} = \infty$, we see that $$ 0 = \lim_{n\to\infty} \frac{\log (n^{\epsilon/2})}{(n^{\epsilon/2})^2} = \lim_{n\to\infty} \frac{\frac{\epsilon}{2} \log n}{n^\epsilon}. $$ It follows that $$ \lim_{n\to\infty} \frac{\log n}{n^\epsilon} = 0. $$

$\endgroup$
1
$\begingroup$

Let us first prove the probably more common fact, any growing exponential function grows faster than a monomial. (You can just skip this part if it is known to you.)

For any $\alpha>0$, $\beta > 1$, we can choose an integer $c\gt \alpha$. Applying L'Hôpital's rule $c$ times we get

$$0\le\lim_{x\to\infty}\frac{x^\alpha}{\beta^x}\le\lim_{x\to\infty}\frac{x^c}{\beta^x} 0=\lim_{x\to\infty}\frac{cx^{c-1}}{(\log\beta)\beta^x}\\ =\lim_{x\to\infty}\frac{cx^{c-1}}{(\log\beta)\beta^x}=\lim_{x\to\infty}\frac{c(c-1)x^{c-2}}{(\log\beta)^2\beta^x}\\ =\cdots=\lim_{x\to\infty}\frac{c(c-1)\cdots2\cdot1}{(\log\beta)^c\beta^x}=0$$ where the last equality holds since $\beta^x = (1+(1-\beta))^x\gt1+x(1-\beta)\to\infty$ as $x\to\infty$.

So, $x^\alpha = o(\beta^x)$ for any $\alpha>0$, $\beta > 1$.


Let $\alpha = 1, \beta=e^\epsilon$. By a change of variable $x=\log n$, we can see that $$\log n = o(e^{\epsilon\log n})=o(n^\epsilon)$$ Similarly, we have $$\log\log n = o((\log n)^\epsilon) \quad\text{ for any }\epsilon\gt 0 $$ $$e^n = o(\lambda^{e^n}) \quad\text{ for any }\lambda\gt 1 $$

$\endgroup$
-1
$\begingroup$

Your solution is one tiny step away from proving that the limit is zero.

But obviously log n has no upper limit. And if eps is small, it will take a very large n to make n^eps < log n.

I recommend that you use a spreadsheet and try this. If eps = 0.001 then n must be as large as 10^1000 just to make n^eps = 10.

$\endgroup$
  • 1
    $\begingroup$ I'm confused. What role does a spreadsheet have in proving that $n^{\varepsilon} < \log n$ for all $\varepsilon$ and all large enough $n$? $\endgroup$ – David Richerby Oct 11 '16 at 13:56
  • $\begingroup$ Well, it helps you getting your head out of the clouds. And realising that "large enough" is very, very, very large if eps is small. $\endgroup$ – gnasher729 Oct 11 '16 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.