Consider the following recurrence: T(n) = 2T(n/2)+nlgn
Let's use a base-case of T (2) = 2 and let's assume n is a power of 2.
Part (a) "Guess and prove by induction" method, considering the following steps.
Step i. Try to prove by induction that T(n) <= cnlgn. (assume inductively that T(n') <= cn'lgn'for all n' < n and try to show it holds for n. This guess is incorrect and so your proof should fail.) Point out where this proof fails.
Step ii. Use the way the above proof failed to suggest a better guess g(n). Explain this guess and prove by induction that T (n)<= g(n) as desired.
Step iii. give a proof by induction to show that T(n) >= c'g(n) where c' > 0 is some constant andg(n) is your guess from (b). Combining this with (b), this implies that T (n) = bigtheta(g(n)).
Part (b) Solve the recurrence using the recursion trees method.
You have to satisfy the requirements specified in the instruction.