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

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)

---

Another thing to note is the Randomized Quicksort may improve the performance, but the time complexity remains the same, Best and Avg case - $O(nlogn)$ and Worst case - $O(n^2)$

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

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

---

@annie1234 remember sometimes overthinking also gives you penalty unless you will be in correct depth 

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

---

psych0 Ok

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.

Answer 5

Answer: (B) — T(n)≤T(n/5)+T(4n/5)+n.

Reason : pivot guarantees both parts have at least n/5 elements, so the two subproblems have sizes between n/5 and 4n/5. The worst split (for recurrence) is one of size ⌊n/5⌋ and the other ⌊4n/5⌋. 

Add linear-time partitioning work Θ(n), giving

T(n)≤T(n/5)+T(4n/5)+Θ(n).

With this bound the total cost is Θ(nlog⁡n) since each level costs Θ(n) and depth is O(log⁡n).