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) <= 2T(n/5) + n
B. T(n) <= T(n/5) + T(4n/5) + n
C. T(n) <= 2T(4n/5) + n
D. T(n) <= 2T(n/2) + n
The Answer to this question is B. My doubt is that why can't the answer be C? My logic is that if there are (n/5) elements on one side and (4n/5) on the other, then T(n)= T(n/5) + T(4n/5) + n. Here, 4n/5 > n/5 so definitely, time taken will be less than 2T(4n/5) + n, if elements are more than (n/5)( since it is given 'AT LEAST').
Where am I going wrong?