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

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let $T(n)$ be the number of comparisons required to sort $n$ elements. Then

  1. $T(n) \leq 2T(n/5) + n$

  2. $T(n) \leq T(n/5) + T(4n/5) + n$

  3. $T(n) \leq 2T(4n/5) + n$

  4. $T(n) \leq 2T(n/2) + n$

asked in Algorithms by Veteran (52.1k points)
edited by | 2.8k views
Each of which. means?

If one of the list expands ( > n/5), then the other one shrinks ( < 4n/5) which results in more balanced tree. So T(n) is less in this case.

Here the worst case is when one of the list is of size exactly n/5 & the other exactly 4n/5 resulting in skewed tree. So comparatively T(n) is maximum in this case.

So overall T(n) ≤ T(n/5) + T(4n/5) + n

C. T(n)<=2T(4n/5)+n
@Magma can u please explain.
why option C is not correct ??

T(n) = T(n/5) + T(4n/5) + O(n)

T(n) <= 2*T(4n/5) + O(n)

right ??
Option C would have been correct incase option B was missing.But since we have a more appropriate choice among the options, its B
In my opinion in that case   inequality shouldn't be  there in Option B

it should be   T(n) = T(n/5) + T(4n/5) + O(n) only
I may be wrong also
@magma, I think T(n) will be less than the given expression in case it is not divided in the ratio of 1/5 and 4/5 because it is atleast 1/5.Like eg,if we take the partition as 2/5 and 3/5 then The(n) will be less.Please correct me if I am wrong
Ans is B.
In  T(n) = T(n/5) + T(4n/5) + O(n)

n is taken in the worst case. Its possible to be computed in less than n swaps of quick sort.
So <= inequality is necessay.
This procedure  splits the list in 1:4, so recurrence eq. should be


Solve this we get O(nlogn).

2 Answers

+26 votes
Best answer

$T(n) \leq T(n/5) + T(4n/5) + n$

One part contains $n/5$ elements
and the other part contains $4n/5$ elements
$+n$ is common to all options, so we need not to worry about it.

Hence, answer is option B.

answered by Boss (30.5k points)
edited by

Even in case of n/2, still satisfies the condition; contains at least 1/5th condition;and 2T(n/2) + n < T(n/5) + T(4n/5) + n.

So its safe to go with option B.

@Arjun sir

Why not option d is the answer . Question is saying about number of elements into sublists each of containg atleast one fifth .....  a/c to option d the stack space will be  logn base 2 which is lesser than stqck space of option b  . In option b stack space will be logn base 5/4 which is greater than logn base 2  .  Please correct me  if i am wrong . Thanks
Because we always take close answer
@Arjun sir here option B is exactly equal to the required answer we dont need an approximation right ?? if we take approximation even C will be right as if we increase the number of elements the time complexity will increase and time of our required algorithm will be less than that
The answer doesn't explain the "atleast" one fifth part.. :(
There is an explanation for the $n$ part too - we know that quicksort takes linear amount of time to partition. Hence, the $n$ term.


hey, even though we go for more than "1/5" we will approach to better performance of quick sort. And anyhow at extreme we have to satisfy at least 1/5 , so i guess this recurrence relation will give an upper bound on QS.

Please correct me if something wrong.

+11 votes
The answer is B.

With 1/5 elements on one side giving T(n/5) and 4n/5 on the other side, giving T(4n/5).

and n is the pivot selection time.
answered by Boss (19.9k points)
n is partition time . i think so . is it ???
Yes @xor

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,811 questions
54,540 answers
75,603 users