The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 votes

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 (52.1k points)
edited by | 4.2k views
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)?$

4 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
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.
Plzzz Any one clarify my doubt

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.


I got it thank you
@ 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.
but it is not mentioned to take elements in sorted order

@MiNiPanda  @Mk Utkarsh

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


@Sachin Mittal 1 

Why master's theorem is not working here??


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 @MiNiPanda @srestha   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. 

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).
+5 votes

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

answered by Loyal (6.7k points)
Explain .....
+1 vote

option b

answered by Boss (34.2k points)
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 (175 points)

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
49,807 questions
54,507 answers
74,952 users