1,127 views

3 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)
0 votes
0 votes
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 .

Related questions

1 votes
1 votes
1 answer
1
rahul sharma 5 asked Mar 9, 2018
1,282 views
Consider the modified merge sort where we divide array into 5 equal sub arrays instead if 2(as in standard merge sort).What is the time complexity if modified merge sort?...
1 votes
1 votes
0 answers
2
0 votes
0 votes
0 answers
3
4 votes
4 votes
1 answer
4
Shivi rao asked Oct 10, 2017
1,513 views
True or FalseMerge sort on Linked list takes O(nlogn)