edited by
21,126 views
48 votes
48 votes

In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort?

  1. $\Theta(n)$

  2. $\Theta(n \log  n)$

  3. $\Theta(n^2)$

  4. $\Theta(n^2 \log  n)$

edited by

5 Answers

Best answer
51 votes
51 votes

Answer is B.

$T(n)= O(n)$ pivot selection time $ + T(n/4 - 1) + T(3n/4)$

which'll give $\Theta\left(n \log n\right)$.

Pivot selection complexity is given in questions. Pivot being the $(n/4)$th smallest element, once it is found, we have two sub arrays- one of size $(n/4 - 1)$ and other of size $(3n/4)$ and for both of these we solve recursively.

edited by
8 votes
8 votes
CLRS book mentions that any split of constant proportionality produces a time complexity for quicksort which is same as average case, i.e Θ( n log n ). Here as we know the split is n/4 : 3n/4...we know time complexity will remain Θ( n log n ) .
3 votes
3 votes

Note:

$4^{th}$ smallest will go to $4^{th}$ place.

$7^{th}$ smallest will go to $7^{th}$ place.

$\dfrac{n}{4}^{th}$ smallest will go to $\dfrac{n}{4}^{th}$ place.

$\underbrace{\left | \dfrac{n}{4}-1 \right |  \fbox{$\dfrac{n}{4}^{th}$}}$ $\left | n-\dfrac{n}{4} \right |$

$\dfrac{n}{4}\ elements$


$\underbrace{O(n)}$      

$\dfrac{n}{4}^{th}$

smallest element

$+$

$\underbrace{O(1)}$

Swap with

last element

$+$

$\underbrace{O(n)}$

partition

algo

$+$

$T\left(\dfrac{n}{4}-1\right)+T\left(n-\dfrac{n}{4}\right)$


$T(n)=O(n)+O(1)+O(n)+ T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)$

$T(n)=O(n)+ T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)$

$T(n)=O(n\ logn)$

Answer:

Related questions

30 votes
30 votes
2 answers
1
Kathleen asked Sep 22, 2014
27,567 views
What is the number of swaps required to sort $n$ elements using selection sort, in the worst case?$\Theta(n)$$\Theta(n \log n)$$\Theta(n^2)$$\Theta(n^2 \log n)$