TIFR CSE 2012 | Part B | Question: 14

Question

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?

• A. The running time of the algorithm is $\Theta (n).$
• B. The running time of the algorithm is $\Theta (n\log n)$.
• C. The running time of the algorithm is $\Theta (n^{1.5})$.
• D. The running time of the algorithm is $\Theta (n^{2})$.
• E. None of the above.

Comments

In this case, quicksort will be same as merge sort, as the middle element is selected as the pivot.

---

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)$

Answer 1

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.

Comments

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.

---

@`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!

Answer 2

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.

 

Answer 3

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.

Comments

see Best Answer .....