# Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons required to sort array of n elements. Then T(n)<=?

+1 vote
Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons required to sort array of n elements. Then T(n)<=?

(a) T(n) <= 2 T(n/4) + cn

(b) T(n) <= T(n/4) + T(3n/4) + cn

(c) T(n) <= 2 T(3n/4) + cn

(d) T(n) <= T(n/3) + T(3n/4) + cn

I got this question during an interview.

The origin of the question is Quicksort topic in section Sorting of Data Structures & Algorithms II

+1 vote
by (614k points)
selected by

Right option is (b) T(n) <= T(n/4) + T(3n/4) + cn

The explanation is: If there are n/4 elements in one sub-array then T(n/4) comparisons are needed for this sub-array. And T(3n/4) comparison are required for the rest 4n/5 elements, and cn is time required for finding the pivot. If there are more than n/4 elements in one sub-array then other sub-array will have less than 3n/4 elements and time complexity will be less than T(n/4) + T(3n/4) + cn.

+1 vote
+1 vote
+1 vote