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

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

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

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.

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

1
2