GATE CSE 2008 | Question: 43

Question

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

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

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

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

• D. $T(n) \leq 2T(n/2) + n$

Comments

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

---

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)

Answer 1

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

Comments

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.

---

@MiNiPanda 

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

Answer 2

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.

Comments

n is partition time . i think so . is it ???

---

Yes @xor

Answer 3

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

Comments

helpful

Answer 4

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.