7
$\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$
3

3 Answers 3

3
$\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$
0
0
$\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$
2
  • 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$ Oct 11, 2016 at 13:56
  • 1
    $\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, 2016 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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