3
$\begingroup$

I'm trying to prove or disprove that $\log^{k}(n) \in O(\sqrt{n}), \ \forall k > 0$. By using the free version of wolfram and testing some increasing values of $k$ I get that:

$$\lim_{n \rightarrow \infty} \frac{\log^{k}(n)}{\sqrt{n}} = 0$$

And apparently $\log^{k}(n) \in O(\sqrt{n})$, but by trying to solve this limit on paper in order to reach an appropriate proof I would need to keep applying L'Hospital rule indefinitely. Is that what I suppose to be doing? How could I proceed to build this proof?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes. Using L'Hospital:

$\lim_{n \rightarrow \infty} \frac{\ln^k (n)}{\sqrt n} = \lim \frac{k \ln^{k - 1} (n) \frac{1}{n}}{ \frac{1}{\sqrt n }} = \lim \frac{ k \sqrt n \ln^{k -1 } (n) }{ n } = \lim \frac{k \ln^{k-1} (n)}{\sqrt n} = \dots = \lim \frac{k \cdot (k -1) \cdots 2 \ln (n) }{ \sqrt n} = \lim \frac{k! \frac{1}{n}}{\frac{1}{\sqrt n}} = \lim \frac{k!}{\sqrt n} = 0$

I hope I got it right, quite some time since I've used it. I^ve left out the $\frac{1}{2}$ from the $\sqrt n$

$\endgroup$

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.