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
Answer: Option B
This Question Belongs to Data Structure >> Sorting Algorithms
Join The Discussion