Project ForgeAlgorithms
Complexity Analysis
GATE 2008
Hard
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two 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
- AT(n) ≤ 2T(n/5) + n
- T(n) ≤ T(n/5) + T(4n/5) + n
- CT(n) ≤ 2T(4n/5) + n
- DT(n) ≤ 2T(n/2) + n
Explanation
Since each side must have AT LEAST n/5 elements, the worst-case (most unbalanced) valid split is exactly n/5 and 4n/5. Partitioning costs n comparisons at this level, giving the worst-case recurrence T(n) ≤ T(n/5) + T(4n/5) + n.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.