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 16.0k 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 abhilashpanicker29 commented Mar 9, 2016 reply Follow Share can you tell the algo, which gives median in O(n) time? 0 votes 0 votes Anurag_s commented Mar 9, 2016 reply Follow Share https://en.m.wikipedia.org/wiki/Median_of_medians 1 votes 1 votes abhilashpanicker29 commented Mar 9, 2016 reply Follow Share Thanks :) 0 votes 0 votes thor commented Nov 23, 2016 reply Follow Share What if all elements are equal 0 votes 0 votes Prashant. commented Nov 23, 2016 reply Follow Share then also O(nlogn) 0 votes 0 votes vineet.ildm commented Aug 1, 2017 reply Follow Share @prashant can u explain. How it will be O(nlogn) when all elements are same 0 votes 0 votes 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.