in Algorithms
934 views
0 votes
0 votes
what is the recurrence relation for merge sort?
in Algorithms
by
934 views

1 comment

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

2 Answers

0 votes
0 votes
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)
0 votes
0 votes
Reccurrence relation for merge sort is T(n)=2T(n/2)+O(n)