Confusion about O((log n)²) vs O(log n)

Question

I can't find anything good on the internet explaining what O((log n)²) is equal to. I think it's equal to O(log n), by the following argument:

• O(log (log n)²)
  = O(log (log n · log n))
  = O(log log n + log log n)
  = O(2 log log n)
  = O(log log n)
• Removing a 'log' from both sides gives O((log n)²) = O(log n).

Is that valid?

Answer 1

The argument you’re proposing here is an interesting one, but unfortunately it doesn’t work. To see why, let’s “prove” that O(n¹³⁷) = O(n). To do so, notice that

O(log n¹³⁷)

= O(137 log n)

= O(log n).

So dropping the logs from both sides gives us that O(n¹³⁷) = O(n).

But of course, that can’t be right. And the reason why is that while it is the case that if f(n) = O(g(n)) then log n = O(log g(n)), it’s not generally true that log f(n) = O(log g(n)) implies f(n) = O(g(n)).

As to your initial question - it’s not the case that log² n = O(log n). In fact, for any function f that isn’t O(1), it’s not the case that f(n)² = O(f(n)).

Answer 2

If A is bounded above by 2*log(N) then exp(A) is bounded above by exp(2*log(N)) which is larger than exp(log(N)) = N.

Your logic falls apart where you drop the '2' before reapplying the exp().