in Others edited by
915 views
0 votes
0 votes

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} $
in Others edited by
915 views

1 comment

Answer:B
0
0

1 Answer

1 vote
1 vote

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.