# GATE2009-39

7.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)$

edited
1
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
How can you take all elements equal?

The question clearly says $\mathrm{\left (\dfrac{n}{4}\right )^{th}\;\mathbf{smallest}}$ element.

$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
9
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.
15

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
64

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

6
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?
40
$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)$
7
\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
1
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

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

0

Why master's theorem is not working here??

0

why here we assumed that it always be divided in t/4 and 3t/4 as pivot can be anywhwere not neccesaary to be at t/4 th position. @Gate Keeda @Debashish Deka    pls explain ?

as n/4th element smallest element can be at leftmost or rightmost position also. they asked for n/4th smallest element not n/4th position.

0
What if I say that at each level use O(n) time algo to find n/4 smallest element as pivot in this case complexity will be O(n^2logn).
0

@Sachin  can you please elaborate how you got  bigO(nlogn) through your recurrence relation , because we can't apply master theorem here due to different sizes of sub problems ,I'm confused so please explain ,thank you !

0

^ What @Sachin Mittal 1 and @dd are saying is that if $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$, we can also write -:

$T(\frac{n}{4}) + T(\frac{n}{4}) + O(n) \leq T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n) \leq T(\frac{3n}{4}) + T(\frac{3n}{4}) + O(n)$, or

$T(\frac{n}{4}) + T(\frac{n}{4}) + O(n) \leq T(n) \leq T(\frac{3n}{4}) + T(\frac{3n}{4}) + O(n)$

This gives us both our upper and lower bounds on $T(n)$, which we can now find by using the master theorem independently on the LHS and RHS. It's genius.

0
If the list is broken into n/4 and 3n/4 then the logic above works pretty fine, whereas if I have 654231, here the n/4th smallest element is 1 and that breaks the list into such 0 + n-2 + c(1), here I can get to the complexity of O(n^2). Can anyone show me why I am wrong here?

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

0
Explain .....

option b

CLRS book mentions that any split of constant proportionality produces a time complexity for quicksort which is same as average case, i.e Θ( n log n ). Here as we know the split is n/4 : 3n/4...we know time complexity will remain Θ( n log n ) .
1 vote
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
1 vote

Hope this helps:)

Note:

$4^{th}$ smallest will go to $4^{th}$ place.

$7^{th}$ smallest will go to $7^{th}$ place.

$\dfrac{n}{4}^{th}$ smallest will go to $\dfrac{n}{4}^{th}$ place.

$\underbrace{\left | \dfrac{n}{4}-1 \right | \fbox{$\dfrac{n}{4}^{th}$}}$ $\left | n-\dfrac{n}{4} \right |$

$\dfrac{n}{4}\ elements$

$\underbrace{O(n)}$

$\dfrac{n}{4}^{th}$

smallest element

$+$

$\underbrace{O(1)}$

Swap with

last element

$+$

$\underbrace{O(n)}$

partition

algo

$+$

$T\left(\dfrac{n}{4}-1\right)+T\left(n-\dfrac{n}{4}\right)$

$T(n)=O(n)+O(1)+O(n)+ T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)$

$T(n)=O(n)+ T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)$

$T(n)=O(n\ logn)$

## Related questions

1
3.2k views
What is the number of swaps required to sort $n$ elements using selection sort, in the worst case? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest common ... major order of $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest ... $\text{expr2} = \max\left(l\left(i-1, j-1\right), l\left(i,j\right)\right)$
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm? $\text{(b, e) (e, f) (a, c) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (a, c) (f, g) (b, c) (c, d)}$ $\text{(b, e) (a, c) (e, f) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (b, c) (a, c) (f, g) (c, d)}$