retagged by
582 views

1 Answer

1 votes
1 votes

The question means to ask out of the comparision based sorting algos that we have , what is the lowest possible function corresponding to worst case scenario of number of comparisions..

So this is O(nlogn) as we have worst case for mergesort and heapsort = O(nlogn) which are comparision based algos.

We know that in merge() procedure of mergesort , we require comparision..And we know if we have no of elements in each of the 2 array as n/2 and hence the number of comparision in the worst case is given by = n/2 + n/2  = n

And in mergesort is called recursively 2 times on problem size of n/2..Hence the recurrence relation for no of comparision can be written as :

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

==> T(n)  =  O(nlogn)

Hence C) should be the correct answer..

Answer:

Related questions

1 votes
1 votes
1 answer
1
iarnav asked May 4, 2019
834 views
I’ve seen this wikipedia article – https://en.wikipedia.org/wiki/Comparison_sortAlso see this link – https://gateoverflow.in/32948/minimum-number-of-comparisonshttp...
1 votes
1 votes
1 answer
3
geet.m asked Jun 29, 2016
476 views
3 votes
3 votes
3 answers
4
sunil sarode asked Jan 23, 2018
2,915 views
I am not able to get this formula (number of input * number of digit *base of number )I am not getting how base of number is important ?Thanks :)