Question

solve the recurrence relation(of merge sort algorithm) T(n) = 2T(n/2) + c*n and T(1)=1 using recursion tree method.​

Answer 1

Answer:

Time Complexity Analysis-

In merge sort, we divide the array into two (nearly) equal halves and solve them recursively using merge sort only. Finally, we merge these two sub arrays using merge procedure which takes Θ(n) time as explained above. On solving this recurrence relation, we get T(n) = Θ(nlogn).