How do I use L'Hopital's rule to determine if $\log^kN$ is $o(N)$ for any constant $k$?

Question

How do I apply L'Hopital's rule to see if $\log^kN$ is $o(N)$ (small $o$) for any constant $k$?

I understand I should keep finding the derivatives of both functions and stop if I can clearly identify a value but I don't know how to show it.

Answer 1

You want to prove that $\log^k(N)$ is $o(N)$. By definition of small-oh, you want to show that $$\frac{\log^k(N)}{N}\to 0,$$ for $N\to\infty$. If the limit exists, we have by L'Hôpital that $$\lim_{N\to\infty}\frac{\log^k(N)}{N} = \lim_{N\to\infty}\frac{\frac{d}{dN}\log^k(N)}{\frac{d}{dN}N} = \lim_{N\to\infty} \frac{k\log^{k-1}(N)\frac{1}{N}}{1} = k\lim_{N\to\infty} \frac{\log^{k-1}(N)}{N}.$$ Applying L'Hôpital $k-1$ more times, we get $$k\lim_{N\to\infty} \frac{\log^{k-1}(N)}{N} = k\cdot (k-1)\cdots 2\cdot 1\lim_{N\to\infty} \frac{1}{N} = 0,$$ which is what we set out to show.

Edit: Elaborating on the last line. If you apply L'Hôpital one time to the limit $k\lim_{N\to\infty} \frac{\log^{k-1}(N)}{N}$, then you get $$k\lim_{N\to\infty} \frac{\log^{k-1}(N)}{N} = k\lim_{N\to\infty} \frac{(k-1)\log^{k-2}(N)\frac{1}{N}}{1}=k(k-1)\lim_{N\to\infty} \frac{\log^{k-2}(N)}{N}.$$

You see that the exponent of $\log$ falls by $1$ each time we apply L'Hôpital, and notice also the factor that we get out front. If I apply L'Hôpital again to $k(k-1)\lim_{N\to\infty} \frac{\log^{k-2}(N)}{N}$, I get $k(k-1)(k-2)\lim_{N\to\infty} \frac{\log^{k-3}(N)}{N}$, and so forth. At some point, the exponent of $\log$ will be $0$, which is why I end up with $k(k-1)\cdots 2\cdot 1\lim_{N\to\infty}\frac{1}{N}$.

Answer 2

You can also simply use that $$ \frac{\log^k N}{N}=\frac{(2k)^k}{\sqrt N}·\left(\frac{\log\sqrt[2k]N}{\sqrt[2k]N}\right)^k $$ and then use that $\log x/x$ is bounded.