3 votes 3 votes Consider a scenario of modified quick sort, where we have given an input sorted array A[1 .. . n], all elements of array are distinct and n >=3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity of modified quick sort? a.O($n^{2}$) b.O(nlogn) c.O($n^{2}$logn) d.O(nloglogn) Algorithms algorithms sorting quick-sort made-easy-test-series + – newdreamz a1-z0 asked Jan 21, 2019 • edited Mar 3, 2019 by ajaysoni1924 newdreamz a1-z0 1.6k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply noob_coder commented Apr 30, 2019 reply Follow Share It should be O(nlogn) in worst case because, selecting median as pivot means it will be always placed at the middle after applying partition algorithm. 0 votes 0 votes saikumar kella commented Nov 19, 2019 reply Follow Share B is the correct option Because for every split occur at the middle . 0 votes 0 votes smsubham commented Dec 18, 2019 reply Follow Share See this https://www.geeksforgeeks.org/can-quicksort-implemented-onlogn-worst-case-time-complexity/ 0 votes 0 votes Mohit Kumar 6 commented Apr 26, 2020 reply Follow Share what is that means[ Pivot is the median of set of 3 elements ]. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Worst case would be Θ($n^2$) because input array given is already sorted. Saurabh Pandey answered Jun 10, 2019 • reshown Jan 30, 2020 by Saurabh Pandey Saurabh Pandey comment Share Follow See all 2 Comments See all 2 2 Comments reply smsubham commented Dec 18, 2019 reply Follow Share No. See this: https://www.geeksforgeeks.org/can-quicksort-implemented-onlogn-worst-case-time-complexity/ 1 votes 1 votes Hradesh patel commented Dec 18, 2019 reply Follow Share i think O(nlogn) is right answer.... 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes B should be the correct option. SaurabhKatkar answered Nov 14, 2019 SaurabhKatkar comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Option B is the correct answer. lets consider an array 1,2,3,4,5 according to the question median of an array = median(1,3,5)= 3. so the array is divided into almost equal halves and for that time complexity would be O(nlogn) Avinash31 answered Jul 11, 2020 Avinash31 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes option B) O(nlogn) is correct , because everytime array is divided into almost equal parts. Sanandan answered Sep 9, 2020 Sanandan comment Share Follow See all 0 reply Please log in or register to add a comment.