The Big-O of the following equation

Question

How to get the upper bound of the following equation, thanks!

2log(mn/2) + 4log(mn/4) + ... + mlog(mn/m)

Answer 1

This sum works out to Θ(m log n).

Let's start by rewriting

2^k log (mn / 2^k) = 2^k(log mn - k)

Now, we have the sum

Σ_k=1^{log m} 2^k (log mn - k)

= Σ_k=1^{log m} (2^k log mn - k 2^k)

= log mn Σ_k=1^{log m} 2^k - Σ_k=1^{log m} k 2^k

That first sum is the sum of a geometric series. It simplifies to 2^{1 + log m} - 2 = 2m - 2. That means that we're left with

2m log mn - 2log mn - Σ_k=1^{log m} k 2^k

That leaves us with the task of simplifying the sum k2^k over some range. This is an arithmetico-geometric sum. If we imagine this sum ranging from 2 (inclusive) to some upper bound q, then the sum works out to q2^q+1.

(q+1)2^q+1 - 2 + 2(2 - 2^q+1)

= (q+1)2^q+1 - 2 + 4 - 2·2^q+1

= (q - 1)2^q+1 + 2

You can check that this formula is correct by plugging in different values of q.

In our case, q = log m, so the sum we want works out to

(log m - 1)2^{1 + log m} + 2

= (log m - 1)(2m) + 2

= 2m log m - 2m + 2

So our overall sum works out to

2m log mn - 2log mn - Σ_k=1^{log mn} k 2^k

= 2m log mn - 2log mn - (2m log m - 2m + 2)

= 2m log mn - 2log mn - 2m log m + 2m - 2

= 2m (log mn - log m + 1) - 2log mn - 2

= 2m (log n + 1) - 2 log mn - 2

Θ(m log n).

Hope this helps!