0

I'm studying asymptotic analysis and I have a doubt about this comparison.

So, is $\log(\sqrt{n})$ thus $\log(n^{1/2}) = O(\log(n))$?

Or are they asymptotically equivalent?

Especially Lime
  • 40,828
Simone C.
  • 225
  • 4
    $\log \sqrt n = \dfrac12 \log n = \mathcal O \left( \log n \right)$, because multiplying by a constant does not change the asymptotic behaviour. – Kenny Lau Apr 27 '17 at 10:39

1 Answers1

0

Yes, $\log\sqrt n=\frac12\log n$, so we have $\log\sqrt n\leq C\log n$ with $C=\frac12$, and so $\log\sqrt n=O(\log n)$.

Especially Lime
  • 40,828