158 views

Write Recurrence of Quick Sort in worst case.

1. $\text{T(n)} = \text{T (n-1)} + 1$
2. $\text{T(n)} = \text{T (n-1) + n}$
3. $\text{T(n)} = 2 \text{T (n-1) + n}$
4. $\text{T(n)} = \text{ T (n/3) + T (2n/2) + n}$

### Subscribe to GO Classes for GATE CSE 2022

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.

1
152 views