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?
What is the difference between the above question and this https://gateoverflow.in/2048/gate2014-3-14 ?
https://gateoverflow.in/1830/gate2006-52
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)$
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.
@`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).
@rohith1001,
yes absolutely but only in the worst case right!
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.
64.3k questions
77.9k answers
244k comments
80.0k users