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
$T(n) \leq 2T(n/5) + n$
$T(n) \leq T(n/5) + T(4n/5) + n$
$T(n) \leq 2T(4n/5) + n$
$T(n) \leq 2T(n/2) + n$
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
https://gateoverflow.in/455/gate2008-43
Bhagyashree Mukherje Sandy Sharma thanks
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)
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.
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.
@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.
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
GATE Overflow