The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
3.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 (59.7k points)
edited by | 3.4k 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.9k 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
+39

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

+4
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?
+22
$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.
+2
@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
0
@ Arjun sir can you explain how to interperet recurrence relation using statement and then how to solve it.if it is simple then am able to solve it using master theoram but if it is complicated then am fail plz help.
0
but it is not mentioned to take elements in sorted order
+1

@MiNiPanda  @Mk Utkarsh

 "I tried the same ,  why masters method" failed here ?

0

@Sachin Mittal 1 

Why master's theorem is not working here??

+3 votes

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

answered by Loyal (6.9k 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 (99 points)
Answer:

Related questions



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

44,147 questions
49,639 answers
163,289 comments
65,807 users