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 2k 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)
It's fine to switch back and forth between n and 2k as needed because you're assuming that n = 2k. 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(2k-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 / 2i, 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!