principleMinor
Compare log^k(n) with n^(1/2)
Viewed 0 times
withcomparelog
Problem
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?
$$\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?
Solution
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$
$\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$
Context
StackExchange Computer Science Q#115566, answer score: 2
Revisions (0)
No revisions yet.