Does it simplify to $O(\log n)$ or $O(\log^2 n)$ or something else entirely? I am a bit stuck on this one.

  • $\begingroup$ While $O(n)$ looks the most simple upper bound, you may be looking for a tight one - $\Theta$. $\endgroup$ – greybeard Apr 23 '20 at 4:48

As $\log(n) \times \log(n) = \log^2(n)$, you can say $\log(n) \times \log(n) = O(\log^2(n))$.Moreover, as $\lim_{n\to\infty}\frac{\log(n)}{\log^2(n)} = 0$, you can't write $\log(n) \times \log(n) = O(\log(n))$, but you can write $\log(n) \times \log(n) = \omega(\log(n))$.


One more way of approaching these type of questions if you have slightest idea of possible answers is as follows:

The questions is: What does $(log $ n).($log $ n) simplify to in Big O notation(By Big O I assume you mean the tightest upper bound)

The possible answers provided are: $𝑂(log $ n) and $O(log^2$ n)

Solution: Let us take log of all the above three terms

  1. $log ((log $ n).($log $ n)) = $loglog$ n + $loglog$ n = 2$(loglog$ n)
  2. $log (log$ n) = $loglog$ n
  3. $log (log^2$ n) = 2($loglog$ n)

Don't ignore the constants after taking the log.

You can now clearly see that:

($log $ n).($log $ n) = $O$($log^2$ n)


($log $ n).($log $ n) = 𝜔($log$ n)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.