Asymptotics: Why is $\log^2(n) \in O(n)$?

Question

I know that $(\log_{2}(n))^2 \in O(n)$, but right now I don't really see how to prove it, even though I assume it's fairly easy. Could anyone help me out please?

Answer 1

Using the big-O notation with the limit superior we can say that $$ \lim\sup_{x\rightarrow \infty} |\dfrac{\log_2^2 n}{n}| < \infty \implies \log_2^2 n \in O(n) $$

The limit on the left is equal to 0, as $n$ grows significantly faster than $\log_2^2n$

Answer 2

L'Hôpital's rule can be used to see that $$\lim_{n\to\infty}\dfrac {\ln^2n}n=\lim_{n\to\infty}\dfrac {\frac{2\ln n}n}1=\lim_{n\to\infty}\dfrac {2\ln n}n=\lim_{n\to\infty}\dfrac {\frac2n}1=\lim_{n\to\infty}\dfrac 2n=0.$$

So in fact $\ln^2n=o(n)$.

Answer 3

Actually, $\log(n) \in O(n^c)$ for any $c > 0$. This implies that $\log(n) < K(c)n^c$ for some $K(c)$ for all large enough $n$, so $(\log(n))^{1/c} \lt (K(c))^{1/c}n $ so $(\log(n))^{1/c} \in O(n) $.

Then set $c = 1/2$.

To show $\log(n) \in O(n^c)$:

$\begin{array}\\ \log(n) &=\int_1^n \dfrac{dt}{t}\\ &=\int_1^n t^{-1}dt\\ &\lt\int_1^n t^{-1+c}dt \qquad\text{since } t^{-1} < t^{-1+c}\\ &=\dfrac{t^{c}}{c}|_1^n\\ &=\dfrac{n^{c}-1}{c}\\ &<\dfrac{n^{c}}{c}\\ &\in O(n^c)\\ \end{array} $