2.6k views

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 | 2.6k views

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
+7
T(n)=T(n/4-1)+T(3n/4)+O(n)   [here -1 is for subtracting pivot]

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

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

+1
@arjun sir

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

then n/4 =8/4=2...so 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
+29

..................

+1
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?
+17
$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 ]$
$=\mathcal{O}(nlog_{\frac{4}{3}}n)$

To have lower bound,
$T(n)=2T\left ( \frac{n}{4} \right )+O(n)$
$=\Omega(nlog_4n)$
+3
\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*}
+1
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.
0
@Sachin Mittal 1 Can you please explain where prasitamukherjee has gone wrong?Because I did the same thing.
0
fine explanation

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

0
Explain .....