Solving the recurrence W(n) = W(n / 2) + n log n?

Question

Please verify my logic to see if what I'm attempting is valid or shady.

W(n) = W(n/2) + nlg(n)

W(1) = 1

n =2^k 

By trying the pattern

line 1 : W (2^k) = W(2^k-1) + nlgn

line 2 :         = W(2^k-2) + nlgn + nlgn

...

line i :         = W(2^k-i) + i*nlgn

and then solve the rest for i.

I just want to make sure it's cool if I substitute in 2^k in one place (on line 1) but not in the other for the n lg n.

I find by subbing in 2^k for 2^k lg(2^k) gets really greasy.

Any thoughts are welcome (specifically if I should be subbing in 2^k, and if I should then how would you suggest the solution)

Answer 1

It's fine to switch back and forth between n and 2^k as needed because you're assuming that n = 2^k. However, that doesn't mean that what you have above is correct. Remember that as n decreases, the value of n log n keeps decreasing as well, so it isn't the case that the statement

line i = W(2^k-i) + i * n lg n

is true.

Let's use the iteration method one more time:

W(n) = W(n / 2) + n log n

= (W(n / 4) + (n/2) log (n/2)) + n log n

= W(n / 4) + (n/2) (log n - 1) + n log n

= W(n / 4) + n log n / 2 - n / 2 + n log n

= W(n / 4) + (1 + 1/2) n log n - n / 2

= (W(n / 8) + (n / 4) log(n/4)) + (1 + 1/2) n log n - n / 2

= W(n / 8) + (n / 4) (log n - 2) + (1 + 1/2) n log n - n / 2

= W(n / 8) + n log n / 4 - n / 2 + (1 + 1/2) log n - n / 2

= W(n / 8) + (1 + 1/2 + 1/4) n log n - n

= (W(n / 16) + (n / 8) log(n/8)) + (1 + 1/2 + 1/4) n log n - n

= W(n / 16) + (n / 8) (log n - 3)) + (1 + 1/2 + 1/4) n log n - n

= W(n / 16) + n log n / 8 - 3n / 8 + (1 + 1/2 + 1/4) n log n - n

= W(n / 16) + (1 + 1/2 + 1/4 + 1/8) n log n - n - 3/8n

We can look at this to see if we spot a pattern. First, notice that the n log n term has a coefficient of (1 + 1/2 + 1/4 + 1/8 + ...) as we keep expanding outward. This series converges to 2, so when the iteration stops that term will be between n log n and 2n log n. Next, look at the coefficient of the -n term. If you look closely, you'll notice that this coefficient is -1 times

(1 / 2 + 2 / 4 + 3 / 8 + 4 / 16 + 5 / 32 + ... )

This is the sum of i / 2ⁱ, which converges to 2. Therefore, if we iterate this process, we'll find at each step that the value is Θ(n log n) - Θ(n), so the overall recurrence solves to Θ(n log n).

Hope this helps!