I'd like to show that for all $\epsilon > 0$, there exists an $N$ such that for all $n \geq N$ the following holds: $n^\epsilon > \log(n)$. I'm having trouble justifying this.
My intuition says this should hold. Writing $n = 2^k$ gives an inequality of the form $(2^\epsilon)^k > k$. This should hold for sufficiently large $k$ (and therefore $n$) because $2^\epsilon > 1$, so the function $(2^\epsilon)^k$ grows much faster than $k$. (This is also the approach described in this question.)
However, I was wondering if there is a more "rigorous" way to justify this inequality.
Answer
Provided you have proved L'Hôpital's rule (as you should have in a real analysis course), this is pretty straightforward.
Fix $\epsilon>0$, we have
$$
\lim_{n\rightarrow \infty}\frac{\log n}{n^\epsilon}\stackrel{\text{L'Hôpital's rule}}{=} \lim_{n\rightarrow \infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}=0<1
$$
Proving that for sufficiently large $n$, $\log n
No comments:
Post a Comment