How does one prove (log(n))^2 is O(n)?

Question

---

How does one prove that $(\log_{\,2}(n))^{2}$ is $O(n)$ ?

---

Using induction on $n$, one can easily show $n \lt 2^{n}$ for all integers $n \ge 1$ .

Since $\log_{\,2}$ is strictly increasing, it follows that $\log_{\,2}(n) \lt n$ for all integers $n \ge 1$, and hence $\log_{\,2}(n)$ is $O(n)$ .

I would like to (but am not yet able to) find the proof that $(\log_{\,2}(n))^{2}$ is $O(n)$ .

It appears that $\log_{\,2}(n) \lt \sqrt{n}$ for all $n \gt 16$ and if this could be proven it would follow that $(\log_{\,2}(n))^{2} \lt n$ for all $n \gt 16$ .

The Mathematica plot supporting this is …

Plot[{Log2[x], Sqrt[x]}, {x, 1, 30},  PlotLabels -> Placed[Automatic, Right]]

---

Mathematica shows that $y =\log_{\,2}(n)$ and $y = \sqrt{n}$ intersect at $n = 4$ and $n = 16$ …

NSolve[Log2[x] == Sqrt[x], x, Reals]
{{x -> 4.}, {x -> 16.}}

---

Answer 1

To prove that $(\log_{2}(n))^2$ is $O(n)$, we should show that for all $n>n_{0}$, $\log_{2}^2(n)<cn$.

Consider $f(x)=cx-(\log^2 x)$.

Now, $f'(x) = c - \frac{2\log x}{x}$.

As $\frac{\log x}{x}<1$ $\forall x \in R$, we can find values of $c$ such that $f'(x)$ is always positive or $f(x)$ is increasing.

So, if at say $n=n_{0}$, $f(n)>0$ $\implies \log_{2}^2(n)<cn$ $ \forall n\geq n_{0}$, or, $\log_{2}^2(n)$ is $O(n)$.

Answer 2

---

Assuming that $log_{\,2}(x) \in O(x)$, I believe that the following argument demonstrates that $\left( log_{\,2}(x) \right)^{2} \in O( x )$ …

• $log_{\,2}(x) \in O(x)$
• $ \exists \, C, k \in \mathbb{R}^{+} : \forall x \ge k : log_{\,2}(x) \le C \cdot x $
• $ \forall x \ge k^2 : \frac{1}{2} \cdot log_{\,2}(x) = log_{\,2}(\sqrt{x}) \le C \cdot \sqrt{x} $
• $ \forall x \ge k^2 : log_{\,2}(x) \le (2C) \cdot \sqrt{x} $
• $ log_{\,2}(x) \in O( \sqrt{x} ) $
• $ \left( log_{\,2}(x) \cdot log_{\,2}(x) \right) \in O( \, \sqrt{x} \cdot \sqrt{x} \, ) $
• $ \left( log_{\,2}(x) \right)^{2} \in O( x ) $

---

Thanks to all who responded.

---