NIELIT 2021 Dec Scientist B - Section B: 43
in Others edited by
158 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
158 views

1 comment

Answer:B
0
0

Subscribe to GO Classes for GATE CSE 2022

1 Answer

0 votes
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.