15,730 views

1 Answer

Best answer
4 votes
4 votes
Answer C) O(nlogn),  when median selected as pivot, partition method will divide array into equal halves.. so logn level recursion tree will form with cn work(partition method)  at each level..
The recurence would be..
T(n) = 2T(n/2) + Θ(n)
Therefore total time complexity =Θ(nlogn)  in all cases

Note:O(n) time algo available for median finding
https://en.m.wikipedia.org/wiki/Median_of_medians
edited by

Related questions

4 votes
4 votes
3 answers
1
Swati verma asked Jun 21, 2017
7,584 views
Time complexity of quick sort when we take pivot from the middle element
0 votes
0 votes
1 answer
4
Purvi Agrawal asked Oct 13, 2018
3,716 views
In Quicksort let n/7​ th ​ smallest element is chosen using an O(n2​ ) algorithm as thepivot. Calculate the worst case time complexity of the algorithm.