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

user_13977226 0
Viewed 98

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

  • O(log (log n)2)
    = 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)2) = O(log n).

Is that valid?

logarithm math big-o algorithm
2 Answers

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

O(log n137)

= O(137 log n)

= O(log n).

So dropping the logs from both sides gives us that O(n137) = 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 log2 n = O(log n). In fact, for any function f that isn’t O(1), it’s not the case that f(n)2 = O(f(n)).

user_5015570

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().

user_2243700
Related