2.6k 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 | 2.6k views
0
Each of which. means?
+7

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



$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 (31k points)
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.

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)
+6
n is partition time . i think so . is it ???
+1
Yes @xor