Prove Induction T N N Log N Following Recurrence T 1 1 T N 2t N 2 N T X Largest Integer X Q37280335

Prove by induction that T(n) is Θ(n log n) for the followingrecurrence:

T(1) = 1

T(n) = 2T(n/2) + n

****T(x) largest integer of x is less than n/2)****

Answer

T(n) = 2T(n/2) + n = 2^2T(n/2^2) + n + n = 2^3T(n/2^3) + n + n + n …….. = 2^log(n)T(n/2^log(n)) + n + ….. + n + n Number of terms = log(n) = nT(n/n) + n + ….. + n + n

OR

 

OR