8,626 views

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$

Each of which. means?
edited

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

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

Solve this we get O(nlogn).
Worst case:- if $i^{th}$ smallest or greatest is chosen $O(n^{2})$ (here i is constant eg. 5th largest is chosen as pivot)

Best case:- if $n/4$ th smallest or largest $O(nlogn)$
edited

if we chose pivot such that it divide array in $l:m$ ratio then, $T(n) \leq T(\frac{ln}{l+m}) +T(\frac{mn}{l+m}) + \Theta (n)$

NOTE:-  worst case in simple quick sort is O(n^2), we can improve this, by selection algorithm (given in cormen 2nd edition pg 189 read this it hardly take not more than 1/2 hour) so we called randomized quicksort. worst case O(nlogn)

### Subscribe to GO Classes for GATE CSE 2022

$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, the answer is option B.

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.

worst case is T(n/5)+T(4n/5)+n because this is mentioned in the question "at least one-fifth of the elements" and the worst split is n/5 and 4n/5. Because of this A and D are not the answers because in A worst case is 2T(n/5)+n which is less than T(n/5)+T(4n/5)+n similarly D can't be the answer. C cannot be the answer because the equality never holds. Hope this helps.

It is directly from CORMEN

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.

n is partition time . i think so . is it ???
Yes @xor

Those who are confused between B and C .One thing is sure,If B is correct then C is also correct.

i.e,if  T(n)<=T(n/5)+T(4n/5)+n; implies T(n)<2T(4n/5)+n.

Hence,here We will chosse TIGHTEST-BOUND i.e.

Option:B

If you create two list containing 1/5th elements and in other it contains rest of the elements. If you go through the pivot elements it should give you recurrence relation

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

So option B is correct.
by