Perfect Squares - Logarithm Connection (Square roots and logs)

The number of perfect squares up to $n$ is $\lfloor \sqrt{n} \rfloor$. And $\sqrt{n} = n^{1/2} = 2^{\log_2(n) / 2}$.

So $\log_2(\sqrt{n}) = \log_2(n^{1/2}) = \frac{1}{2} \log_2(n)$ by the power rule. Square roots and logarithms are related through exponentiation.

This shows up in many algorithms: computing square roots, checking primality, factoring numbers. All involve logarithmic relationships with the input size.