1

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]]

enter image description here

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.}}
Anne Bauval
  • 34,650
user3134725
  • 151
  • You can prove that $\log_2(n) < \sqrt{n}$ for $n > 16$ by taking the derivative of $\log_2(n) - \sqrt{n}$. – Randall May 07 '23 at 16:35

2 Answers2

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)$.

Adithya
  • 322
1

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.

user3134725
  • 151