18 votes 18 votes Consider the quick sort algorithm on a set of $n$ numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot. Then which of the following statements is TRUE? The running time of the algorithm is $\Theta (n).$ The running time of the algorithm is $\Theta (n\log n)$. The running time of the algorithm is $\Theta (n^{1.5})$. The running time of the algorithm is $\Theta (n^{2})$. None of the above. Algorithms tifr2012 algorithms sorting quick-sort time-complexity + – makhdoom ghaya asked Nov 2, 2015 • edited Nov 21, 2022 by Lakshman Bhaiya makhdoom ghaya 3.7k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply smsubham commented Jan 6, 2018 reply Follow Share In this case, quicksort will be same as merge sort, as the middle element is selected as the pivot. 0 votes 0 votes K ANKITH KUMAR commented Aug 22, 2018 reply Follow Share What is the difference between the above question and this https://gateoverflow.in/2048/gate2014-3-14 ? 0 votes 0 votes Shubhgupta commented Nov 5, 2018 reply Follow Share https://gateoverflow.in/1830/gate2006-52 0 votes 0 votes Gupta731 commented Jun 24, 2020 reply Follow Share Clarifying common doubt: For a sorted array, median lies in the central position. For unsorted array median may not be there in middle. If central element is chosen as the pivot, then time complexity= $O(n^2)$. It will be $O(n^2)$ as long as pivot is from a fixed position. If pivot is chosen from some median element of unsorted array then time complexity= $O(nlogn)$ 0 votes 0 votes Please log in or register to add a comment.
Best answer 25 votes 25 votes Algorithm is choosing $\text{median} = n/2$ smallest element as pivot. Hence, the array is divided as: $$\large \begin{array}{|c|c|} \hline\\ \substack{\LARGE \left (\frac n 2 -1 \right )\\[0.5em] \text{ elements}} \quad&\quad \substack{\text{Median at}\\[0.5em]\LARGE \frac n 2 \text{th}\\[0.5em]\text{location}} \quad&\quad \substack{\LARGE \left (n - \frac n 2 \right )\\[0.5em] \text{ elements}} \quad \\\\ \hline \end{array}$$ Therefore quick sort recurrence relation is given by: $$\begin{align} T(n) &= T \left ( \frac n 2 -1 \right ) + T \left ( n- \frac n 2 \right ) + \Theta(n)\\[1em] &= \Theta ( n \log n) \end{align}$$ Hence, Option B is the correct answer. Umang Raman answered Nov 2, 2015 • edited Nov 15, 2017 by kenzou Umang Raman comment Share Follow See all 10 Comments See all 10 10 Comments reply Vertika Srivastava commented Jan 7, 2016 reply Follow Share When we asay running time of algo is theta(nlogn) we means running time is bounded by nlogn But in worst case when all elements are same then media will be picked in theta(n) but T(n) = T(n-1) + T(0) + theta(n) in this case it will be O(n^2) so how can it be theta n I mean it just says running time - not avg case running time 3 votes 3 votes Brij Mohan Gupta commented Jul 30, 2017 reply Follow Share @Umang i think vertika is right is section of pivot will be last element of the array then it again go to T(n-1) + T(0) + O(n) time comlexcity which will be O(n^2). 1 votes 1 votes Kaluti commented Oct 7, 2017 reply Follow Share what will be time complexity to find median of an array here 0 votes 0 votes Mr_22B commented Nov 4, 2017 reply Follow Share Wow, earlier the same question of previous year gate someone was giving ans $O(n^{2} )$ by having the argument that what if we will have all same elements ? and Now this ans. 0 votes 0 votes Anu007 commented Dec 2, 2017 i edited by Anu007 Dec 2, 2017 reply Follow Share Answer will be O(n2) since distinct elements are not given. 0 votes 0 votes srestha commented Jan 14, 2019 reply Follow Share @Anu007I think ans is right because, here array is already sorted and we are finding middle of it 0 votes 0 votes Astha11 commented Apr 3, 2019 reply Follow Share how are we finding median in O(n)? 0 votes 0 votes `JEET commented Dec 7, 2019 reply Follow Share It is simple just remember the worst case of quick sort. The given case is not the worst case. $\therefore$ It has to be $\mathbf{O(n)}$ only. 0 votes 0 votes rohith1001 commented Dec 14, 2019 reply Follow Share @`JEET It is $\theta$(n log n) and not O(n). We can't have O(n) in any comparison based sorting as the lower bound. (Refer Theorem 5.1) We will need atleast (n log n) time to sort n numbers using any comparison based sorting algorithms. We can't do better than (n log n). 0 votes 0 votes Kiyoshi commented Jun 20, 2021 reply Follow Share @rohith1001, yes absolutely but only in the worst case right! 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Choosing median as a pivot element will not change much in Actual quick sort algorithm. It 's just swaps the median element with 1st element or last of the Array before start of the quick sort which is done in O(1) time and rest procedure will be same it is also known as Randomized quick sort. so O(nlog n) is right answer. Nitesh Singh 2 answered Jun 17, 2018 Nitesh Singh 2 comment Share Follow See all 0 reply Please log in or register to add a comment.
–2 votes –2 votes answer is nlogn because every time selecting median as a pivot elemet will divide the array two equal parts that result in t(n)=t(n/2)+t(n/2)+n after solving using masters theorem answer is nlogn. raviyogi answered Nov 4, 2017 raviyogi comment Share Follow See 1 comment See all 1 1 comment reply Puja Mishra commented Jan 10, 2018 reply Follow Share see Best Answer ..... 0 votes 0 votes Please log in or register to add a comment.