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
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, 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.
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.
Can someone help me understand examples on...