Which of the following recurrence relation is related to worst case time…
2022
Which of the following recurrence relation is related to worst case time complexity of quick sort?
Answer: C. T(n) = T(n–1) + Cn — In Quick Sort: Best/Average Case: Pivot divides the array into two equal halves. Recurrence: T(n) = 2T(n/2) + Cn Complexity: O(n log n) Worst Case: Pivot is…
- A.
T(n) = T(n/2) + C
- B.
T(n) = 2 . T(n/2) + Cn
- C.
T(n) = T(n–1) + Cn
- D.
T(n) = 7 . T(n/2) + Cn2
Attempted by 97 students.
Show answer & explanation
Correct answer: C
In Quick Sort:
Best/Average Case: Pivot divides the array into two equal halves.
Recurrence: T(n) = 2T(n/2) + Cn
Complexity: O(n log n)
Worst Case: Pivot is always the smallest or largest element.
Partitions become 0 and n−1
Recurrence: T(n) = T(n−1) + Cn
Complexity: O(n²)
Example:
The array becomes highly unbalanced at every step, producing the worst-case recurrence.
Answer: C) T(n) = T(n−1) + Cn