The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
3.1k 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 (59.6k points)
edited by | 3.1k views
0
What if I take an array of size n with all elements equal??

That would lead to worst case irrespective of pivot selection.

So , will Time complexity be $\Theta (n^2)?$

3 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
+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.
+8

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
+36

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

+2
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?
+21
$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.
+1
@Sachin Mittal 1 Can you please explain where prasitamukherjee has gone wrong?Because I did the same thing.
0
fine explanation
0
What if I take an array of size n with all elements equal??

That would lead to worst case irrespective of pivot selection.

So , will Time complexity be $\Theta (n^2)?$
0
But the question doesnot mention the list in sorted order how can we say that the pivot divides the list like n/4 and 3n/4.
0
Plzzz Any one clarify my doubt
0

Read the question.. it is mentioned that

the (n/4)th smallest element is selected as pivot

So if it resides at its correct position then the list is divided like n/4 and 3n/4.

 

0
I got it thank you
+3 votes

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

answered by Loyal (6.8k points)
0
Explain .....
0 votes
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
answered by (71 points)


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

40,903 questions
47,558 answers
146,289 comments
62,305 users