Question

Consider the quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists, one of which contains one-fifth of the elements and the remaining elements are contained in the other sub-list. 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

Hint:

In recurrence relations, always include the partitioning cost (e.g., n) along with recursive calls for sub-problems.

Answer 1

The Correct Option is B

In quicksort, the time complexity is determined by the partitioning strategy: - Here, the pivot splits the list into two parts: n/5 and 4n/5. - The recurrence relation becomes: T(n) = T(n/5) + T(4n/5) + n. - The n term accounts for the partitioning step, where comparisons are made for all n elements.