The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+24 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)$

asked in Algorithms by Veteran (59.5k points)
edited by | 2.9k views

2 Answers

+30 votes
Best answer

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.

answered by Boss (19.7k points)
edited by
T(n)=T(n/4-1)+T(3n/4)+O(n)   [here -1 is for subtracting pivot]

then how to solve? Could anybody elaborate?
plzzz elaborate the reccurence relation.

height of  this recurrence tree  is log4/3 n  and cost of every level <=n

so, (n+n+-----log4/3 n times)    =  O(n log4/3n)  

SO ans is B

@arjun sir

suppose we have an array { 8,7,6,4,3,1,9,5}  here n=8

then n/4 =8/ n/4th smallest element =the second smallest element which is 3

after selecting 3 as pivot the sublists are=={8,7,6,4} and {1,9,5}which is not as above


I have done something like this and haven't got ans!!

T(n) <= 2*T(3n/4) + O(n);
By Master's Theorm a=2. b= 4/3, k=1 , p=0.

2> (4/3)^1, which is the first case of Master's theorm, hence : O(n^log2(base 4/3))

Where have I done wrong?
$T(n)=T\left ( \frac{n}{4}-1 \right )+T\left ( \frac{3n}{4}\right )+O(n)$
$\simeq T(n)=T\left ( \frac{n}{4} \right )+T\left ( \frac{3n}{4} \right )+O(n) $

To have upper bound,
 $T(n)=2T\left ( \frac{3n}{4} \right )+O(n)
\left [ \because \frac{3n}{4} > \frac{n}{4} \right ]$

To have lower bound,
 $T(n)=2T\left ( \frac{n}{4} \right )+O(n) $
$\begin{align*} &T(n) \;\; {\large \color{blue}{\bf \leq}} \;\; 2T\left ( \frac{3n}{4} \right ) + O(n) \\ &\left [ \because \frac{3n}{4} > \frac{n}{4} \right ] \\ &\text{Similarly for lower bound case } {\large \color{blue}{\bf \geq }}\\ \end{align*}$
yes u r right, and i knew this already :)
Actually I wanted to take $T'(n)$ after approxing, but i decided to let it be as it is for simplicity.
@Sachin Mittal 1 Can you please explain where prasitamukherjee has gone wrong?Because I did the same thing.
fine explanation
+3 votes

Here, The correct ans is     O ( n log4/3(n))

answered by Loyal (6.8k points)
Explain .....

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,058 questions
45,554 answers
48,911 users