Answer:B

158 views

## 1 Answer

0 votes

The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size *n.* This may occur if the pivot happens to be the smallest or largest element in the list.

In the worst-case for quicksort, the pivot will be the largest or smallest element in the array, so you'll recur on one giant array of size n - 1. To top everything off, the total work done is Θ(n) per level, so the recurrence relation would more appropriately be

$T(n) = T(n - 1) + n$

So, the correct answer should be option B.