Question

Which of the following recurrence relations represents the average case time complexity of QuickSort?

• A. \( T(n) = T(n/4) + T(3n/4) + O(n) \)
• B. \( T(n) = 2T(n/2) + O(n) \)
• C. \( T(n) = \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right] + O(n) \)
• D. \( T(n) = T(1) + T(n-1) + O(n) \)

Hint:

QuickSort worst case: \( T(n) = T(n-1) + O(n) \). QuickSort average case: Expected recurrence over all pivot positions.

Answer 1

The Correct Option is C

Step 1: Understand QuickSort behavior.
QuickSort chooses a pivot and partitions the array into two parts.
If pivot position is \( k \), then recursive calls are: \[ T(k) \quad \text{and} \quad T(n-k-1). \] Step 2: Consider average case.
In average case, pivot can appear at any position from \( 0 \) to \( n-1 \) with equal probability.
Therefore, we take the expected value over all possible splits: \[ \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right]. \] Step 3: Add partition cost.
Partitioning takes linear time: \[ O(n). \] Thus, average case recurrence becomes: \[ T(n) = \frac{1}{n} \sum_{k=0}^{n-1} \left[ T(k) + T(n-k-1) \right] + O(n). \] Step 4: Compare options.
(A) Represents a specific split (not average).
(B) Represents Merge Sort.
(C) Matches expected recurrence for QuickSort.
(D) Represents worst case when pivot is smallest/largest.
Hence, option (C) is correct.