edited by
3,621 views
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?

  1. The running time of the algorithm is $\Theta (n).$
  2. The running time of the algorithm is $\Theta (n\log n)$.
  3. The running time of the algorithm is $\Theta (n^{1.5})$.
  4. The running time of the algorithm is $\Theta (n^{2})$.
  5. None of the above.
edited by

3 Answers

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.

edited by
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.

 

–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.
Answer:

Related questions

13 votes
13 votes
1 answer
2