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: Understanding the Topic
This question asks for the recurrence relation that formally describes the average-case time complexity of the QuickSort algorithm. A recurrence relation for a recursive algorithm expresses its running time on an input of size $n$ in terms of its running time on smaller inputs.
Step 2: Key Approach - Analyzing QuickSort's Behavior
QuickSort works by picking a 'pivot' element and partitioning the array around it. All elements smaller than the pivot go to its left, and all larger elements go to its right. The algorithm then recursively sorts the two sub-arrays. The running time depends heavily on where the pivot ends up after partitioning.

The partitioning step itself takes linear time, $O(n)$.
If the pivot ends up at index $k$ (0-indexed), the two recursive calls will be on sub-arrays of size $k$ and $n-k-1$.
Step 3: Detailed Explanation
A. The General Recurrence:
If the pivot is chosen such that it partitions the array into subproblems of size $k$ and $n-k-1$, the recurrence is: \[ T(n) = T(k) + T(n-k-1) + O(n) \] B. The Average Case:
For the average case analysis, we assume that the pivot is equally likely to end up at any of the $n$ possible positions (from index 0 to $n-1$). To find the average running time, we must consider the cost for every possible pivot position $k$ and average them. \[ \text{Average Cost} = \frac{1}{n} \sum_{k=0}^{n-1} (\text{Cost when pivot is at index } k) \] Substituting the general recurrence into this average: \[ T(n) = \frac{1}{n} \sum_{k=0}^{n-1} [T(k) + T(n-k-1)] + O(n) \] This equation represents the expected running time by averaging over all possible partition outcomes.
C. Evaluating the Options:


(A) $T(n) = T(n/4) + T(3n/4) + O(n)$: This describes a specific, unbalanced partition but is still $O(n \log n)$. It's a possible case, but not the formal average-case recurrence.
(B) $T(n) = 2T(n/2) + O(n)$: This is the recurrence for algorithms like Merge Sort, or the best-case for QuickSort where the pivot perfectly splits the array.
(C) This matches our derived formal recurrence for the average case.
(D) $T(n) = T(n-1) + T(0) + O(n)$ (since $T(1)$ is usually written as $T(0)$ or is a base case): This represents the worst-case scenario where the pivot is always the smallest or largest element.
Step 4: Final Answer
The recurrence relation that correctly models the average-case behavior by considering all possible pivot positions is given in option (C).