GATE CSE 2009 | Question: 39

Question

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?

• A. $\Theta(n)$

• B. $\Theta(n \log  n)$

• C. $\Theta(n^2)$

• D. $\Theta(n^2 \log  n)$

Comments

@Pranavpurkar 

U should use the partition algorithm to place the n/4^th smallest in its position (According to quick sort algorithm ) 

According to partition algorithm 

3 will be placed in the first position or last position as all elements are same ( one of the worst case inputs for quick sort )

But to get the optimised time we are skipping the partition algorithm and directly using the intuition that n/4^th smallest should be present in A[n/4 – 1] so we directly put 3 there and dividing the array accordingly 

But the point is 

Question said that we have to use quick sort algorithm which uses partition algorithm to place the pivot in its correct position but we are using intuition instead of partition algorithm so we are not using the quick sort algorithm, we are using a custom made algorithm to sort which should not be the case

 

---

If all elements are same then still we get TC as O(nlogn) Just use Hoare's Partition Algo which is Given in CLRS question section and You will get best case TC.

 

---

to be precise

\[
\Theta\left(n\log_{\frac{4}{3}} n\right)
\]

Answer 1

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.

Comments

We find the pivot element in the partition step. So in normal case it takes O(1) time and then the partition algo takes O(n) time which in total is O(1 + n) = O(n). Now when an extra algorithm is used of O(n) instead of O(1) for finding the pivot even then the overall complexity is O(n + n) that is O(n) only. Thats why the complexity is still O(nlogn).

---

@Kiyoshi Thanks!!

---

 simple   

Answer 2

option b

Comments

Thankyou @abhishekmehta4u

---

abosolute blessing to the human race

Answer 3

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

Comments

Absloute gem! Thankyou @abhijit_m

Answer 4

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 5

Basically we have worst case in quick sort when all elements are same or sorted. If they are all same then we can't find the (n/4)th smallest element in it.

But if the value are 1 2 3 4 5.

We take pivot 1 here.  Then 2, 3, 4, and 5.

So, no of comparison is n-1 + n-2 + ... + 1.

So n^2 is complexity for worst case which is sorted

Answer 6

Detailed Answer