# What does $(\log n) \cdot (\log n)$ simplify to in Big O notation?

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

• While $O(n)$ looks the most simple upper bound, you may be looking for a tight one - $\Theta$. – 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)

and

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