Question

What is the recurrence for the worst case of quicksort, and what is the time complexity in the worst case?

• A. Recurrence is \( T(n) = T(n-2) + O(n) \) and time complexity is \( O(n^2) \)
• B. Recurrence is \( T(n) = T(n-1) + O(n) \) and time complexity is \( O(n^2) \)
• C. Recurrence is \( T(n) = 2T(n/2) + O(n) \) and time complexity is \( O(n \log n) \)
• D. Recurrence is \( T(n) = T(n/10) + T(9n/10) + O(n) \) and time complexity is \( O(n \log n) \)

Hint:

The worst-case time complexity of quicksort occurs when the pivot is always the smallest or largest element, leading to unbalanced partitions and a recurrence of: \[ T(n) = T(n-1) + O(n) \] which solves to \( O(n^2) \).

Answer 1

The Correct Option is B

Step 1: Understanding Quicksort's Worst-Case Behavior
- Quicksort is a divide-and-conquer sorting algorithm.
- It chooses a pivot and partitions the array into two subarrays.
- Ideally, it partitions into two equal halves, leading to \( O(n \log n) \) time complexity.
- However, in the worst case, the partitioning is highly unbalanced.
Step 2: Worst-Case Recurrence Relation
- If the pivot is always the smallest or largest element, one partition has \( n - 1 \) elements while the other is empty.
- This results in the recurrence: \[ T(n) = T(n-1) + O(n) \]
- Solving this recurrence using the recurrence tree method: \[ T(n) = T(n-1) + O(n) = T(n-2) + O(n) + O(n-1) = O(n^2) \]
Step 3: Evaluating the Options
- (A) Incorrect: \( T(n) = T(n-2) + O(n) \) is not the correct recurrence for quicksort.
- (B) Correct: \( T(n) = T(n-1) + O(n) \) leads to \( O(n^2) \) complexity.
- (C) Incorrect: \( T(n) = 2T(n/2) + O(n) \) is the recurrence for merge sort, which runs in \( O(n \log n) \).
- (D) Incorrect: \( T(n) = T(n/10) + T(9n/10) + O(n) \) results in \( O(n \log n) \), which is not worst-case quicksort.