in Algorithms edited by
16,012 views
46 votes
46 votes

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$

in Algorithms edited by
16.0k views

4 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).
0
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)$
0
0
edited by

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)

2
2

4 Answers

46 votes
46 votes
Best answer

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

edited by

4 Comments

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

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

2
2
It is directly from CORMEN
0
0
12 votes
12 votes
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.

2 Comments

n is partition time . i think so . is it ???
7
7
Yes @xor
1
1
3 votes
3 votes

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

1 comment

helpful
0
0
0 votes
0 votes
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:

Related questions