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 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.
@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
64.3k questions
77.9k answers
244k comments
80.0k users