edited by
929 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} $
edited by

1 Answer

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

Related questions

0 votes
0 votes
0 answers
1
soujanyareddy13 asked Dec 7, 2021
537 views
$y = 10 \cos (1800 \; \pi t) + 20 \cos (2000 \; \pi t) + 10 \cos (220 \; \pi t).$ Find the modulation index $(\mu)$ of the given wave. $0.3$$0.5$$0.7$$1$
0 votes
0 votes
1 answer
2
soujanyareddy13 asked Dec 7, 2021
594 views
Match the following:$$\begin{array} {llll} & \textbf{List-I} & & \textbf{List-II} \\ \text{W.} & \text{Condition coverage} & 1. & \text{Black-box testing} \\ \text{X.} ...
0 votes
0 votes
2 answers
3
soujanyareddy13 asked Dec 7, 2021
3,372 views
_________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms.$\text{NP}$$\text{P}$HardComplete
1 votes
1 votes
1 answer
4
soujanyareddy13 asked Dec 7, 2021
647 views
The following circuit depicts the implementation of __________$\text{XOR}$ Gate$\text{AND}$ Gate$\text{OR}$ Gate$\text{NAND}$ Gate