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

 

asked in Algorithms by Veteran (69k points)
edited by | 2.4k views

2 Answers

+29 votes
Best answer

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 Veteran (19.8k 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/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

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

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

To have lower bound,
 $T(n)=2T\left ( \frac{n}{4} \right )+O(n) $
$=\Omega(nlog_4n)$
$\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
+2 votes

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

answered by Boss (7.2k 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

33,593 questions
40,128 answers
114,021 comments
38,389 users