Any power of logarithm is $O(N)$

Question

This is more of a computer science question but it uses calculus and proof techniques so I think it might be more appropriate here. Basically, how do I prove that,

for any constant $K \geq 1$, that $\log^{K}(N) = O(N)$

Where $O$ denotes the Big O.I am thinking of proving this by induction but not sure what the base case should. In addition to this, I think L'Hopital's rule can be used here with the two functions. Can anyone give me a solid hint on how to start this ? Many thanks !

Answer 1

Hint:

Consider $\lim\limits_{n \to \infty} \dfrac{(\log n)^k}{n} = \lim\limits_{n \to \infty}\dfrac{k (\log n)^{k-1}}{n} = \lim\limits_{n\to\infty}\dfrac{k(k-1)(\log n)^{k-2}}{n} = \cdots = ?$

By using L'Hospital's rule $k$ times, and assuming $k$ is an integer. If $k$ is not an integer, then use same for $(\log n)^{\lceil k \rceil}$.

Answer 2

You can even get a stronger expression, set $\log n =t, n = e^t$, there fore the limit is $$ \lim_{t \to \infty} \frac{t^k}{e^t} = 0 $$ Hence $\log n = o(n)$.