Question

Consider Quick sort algorithm used to sort an array of n distinct randomly ordered element. In every call the pivot is chosen as the first element of the current subarray. Let T(n) denote the expected time to sort the array. Assume that the time to partition is linear in the size of current subarray. Which of the following option represents T(n) in this scenario.

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

Hint:

Remember the recurrence relations for different sorting algorithms and cases: - Quicksort (Worst Case): T(n) = T(n-1) + O(n) $\implies$ O(n$^2$). - Quicksort (Best Case): T(n) = 2T(n/2) + O(n) $\implies$ O(n log n). - Quicksort (Average Case): The one in option (B), which solves to O(n log n). - Mergesort: T(n) = 2T(n/2) + O(n) $\implies$ O(n log n).

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
We need to find the recurrence relation for the {expected} (average-case) time complexity of Quicksort. The key information is that the input array is "randomly ordered" and the pivot is always the first element. Choosing the first element of a randomly ordered array is equivalent to choosing a random pivot.
Step 2: Key Formula or Approach:
The expected time T(n) is the average of the time taken over all possible pivot positions. Since the array is randomly ordered, the first element has an equal probability (1/n) of being the k-th smallest element for any k from 1 to n. If the pivot is the k-th smallest element, it will be placed at index k-1 (0-indexed), leaving subarrays of size k-1 and n-k. The time taken would be the time to sort these two subarrays plus the O(n) partitioning time.
Step 3: Detailed Explanation:
Let's analyze the pivot's final position. Let K be the size of the left subarray after partitioning. If the pivot is the (K+1)-th smallest element, the subarrays will have sizes K and n-1-K. Since any position is equally likely for the pivot, K can be any value from 0 to n-1 with probability 1/n.
The expected time T(n) is the sum of the expected times for each possible pivot position, weighted by the probability of that position occurring, plus the partitioning cost. \[ T(n) = \sum_{K=0}^{n-1} P(\text{pivot position is K}) \times (\text{time for this case}) + O(n) \] The probability of the pivot creating a left partition of size K is 1/n for each K in $\{0, 1, ..., n-1\}$. The time for this case is the time to solve the subproblems: T(K) + T(n-1-K). So, the recurrence relation becomes: \[ T(n) = \sum_{K=0}^{n-1} \frac{1}{n} \times [T(K) + T(n - K - 1)] + O(n) \] This can be rewritten as: \[ T(n) = \frac{1}{n} \sum_{K=0}^{n-1} [T(K) + T(n - K - 1)] + O(n) \] This matches option (B).
Let's look at the other options:
- (A) represents a specific case where the pivot consistently creates a 1/4 and 3/4 split.
- (C) represents the ideal case where the pivot is always the median, which is the recurrence for Mergesort.
- (D) represents the worst-case scenario where the pivot is always the smallest or largest element.
Step 4: Final Answer:
The correct recurrence for the expected time of Quicksort with a random pivot is given by averaging over all possible partition splits, which is represented by option (B).