Merge Sort Doubt

Question

what is the recurrence relation for merge sort?

Comments

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

Answer 1

First merge sort for half array(1to m) that takes T(n/2)

Second merge sort for last half array(m+1to n)

Final phase merging them in O(n) time

So total time complexity=2T(n/2)+O(n/2)

=O(nlogn)

Answer 2

Reccurrence relation for merge sort is T(n)=2T(n/2)+O(n)

Answer 3

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

T(1) = 1

Because in mergesort function we call two time mergesort and at last

we call merge procedure , merge procedure take O(n) and each time we

divide array in half .