+1 vote
in Data Structures & Algorithms II by (110k points)
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 Answer

+1 vote
by (614k points)
selected by
Best answer
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.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.