This is homework for introduction to Algorithms this is what I have below.
- (25 pts) Use the direct unwinding to prove that the recurrence equation T(n)= 2T(n/2)+ nlogn has a lower bound of (nlogn). Hint: It is essentially to prove that T(n) = BigOmegaK(nlogn).
This is what I have I am just confused on the last part I belive my unwinding is correct.
T(n) = 2T(n/2) + nlogn
= 4T(n/4) + nlog(n/2) + nlogn
= 8T(n/8) + nlog(n/4) + nlog(n/2) + nlogn
I am not sure how to prove a lower bound of nlogn?