PA of Algorithms Q106

0. Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into 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

Answer
Comment
Array

Option : B
Explanation :
In quicksort a set of number is reduced to sorting two smaller set. We take first element as key value and combine all other with this. A pivot element which splits list into two sublists each of which at least one fifth of element only (B), i.e. T(n) ≤ T(n/5) + T(4n/5) + n the problem.
Alternately
If one sublist contains 1/5 elements other contains 4/5 elements.
If T(n) number of comparisons for sorting n elements.
So, for 1/5 elements = T(1/5n)
and for 4/5 elements = T(4n/5)
So, T(n) ≤ T(n/5) + T(4n/5) + n.
Here, n = time to spilt

Forgot your password?

I agree with the Terms.