patternMinor
Show that $\log n = o(n^\epsilon)$
Viewed 0 times
showepsilonthatlog
Problem
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$?
$\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$?
Solution
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.
$$
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.
$$
Context
StackExchange Computer Science Q#63340, answer score: 3
Revisions (0)
No revisions yet.