4 votes 4 votes the worst case time complexity of quicksort for an elements when the median is selected as the pivot a. o(n^2) b.o(n) c.o(nlogn) d.o(logn) Algorithms algorithms time-complexity quick-sort + – akankshay asked Mar 9, 2016 akankshay 15.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Anurag_s answered Mar 9, 2016 edited Mar 9, 2016 by abhilashpanicker29 Anurag_s comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments rajatmyname commented Mar 14, 2018 reply Follow Share same recurrence relation will be applied here also 0 votes 0 votes sushmita commented Sep 23, 2018 reply Follow Share if all elements are same then worst case partitioning will occur. How O(nlogn) then? 0 votes 0 votes rajatmyname commented Sep 24, 2018 reply Follow Share Here it doesn't matter all the elements are same or not because it will divide the array in two equal parts which gives the recurrence relation for best case of quick sort 0 votes 0 votes Please log in or register to add a comment.