3.8k 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$

edited | 3.8k views
0
Each of which. means?
+12

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

0
C. T(n)<=2T(4n/5)+n
0
0
0
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 ??
0
Option C would have been correct incase option B was missing.But since we have a more appropriate choice among the options, its B
0
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
0
I may be wrong also
+1
@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
0
Ans is B.
+1
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.
+1
0
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).
0
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)$
+1

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)

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

by Boss
edited
+4

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.

0
@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
0
Because we always take close answer
+1
@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
0
The answer doesn't explain the "atleast" one fifth part.. :(
0
There is an explanation for the $n$ part too - we know that quicksort takes linear amount of time to partition. Hence, the $n$ term.
0

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.

0

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.

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.
by Boss
+6
n is partition time . i think so . is it ???
+1
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

Hope this helps:)

by Active
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.