## 4 Answers

Correct Option:** C**

There are two cases, when Randomized Quick Sort will result into worst case time complexity of $O(n^{2})$

- When all elements are same in the input array, Partition algorithm will divide input array in two sub-arrays, one with $n-1$ elements and second with $0$ element. There is an assumption here that, we are using the same partition algorithm without any modification.

- If the randomised pivot selector happens to select the smallest or largest element N times in a row, we will get the worst possible performance. Though the probability of this particular case is about $\frac{2^{n-1}}{n!}.$

PS: Option D is also correct here as $n^2 = O(n!)$ though $(C)$ is a better choice.

### 8 Comments

The probability is same as getting a skewed binary search tree. :)

The number of possible skewed binary search trees with 'n' nodes = 2$^{n-1}$

When all elements are same in the input array, Partition algorithm will divide input array in two sub-arrays, one with n−1n−1 elements and second with 00 element.

Is this statement also means that worst case occurs only when the array is sorted in increasing or decreasing and choosing either small or large element as the pivot?

Can someone please verify this.

Both the deterministic and randomized quicksort algorithms have the same best-case running times of O($nlogn$) and the same worst-case running times of O(n$^{2}$).The difference is that with the deterministic algorithm, a particular input can elicit that worst-case behavior. With the randomized algorithm, however, no input can always elicit the worst-case behavior. The reason it matters is that, depending on how partitioning is implemented, an input that is already sorted--or almost sorted--can elicit the worst-case behavior in deterministic quicksort.

source: Thomas Coremen

Ans. C

The running time of Randomized QUICKSORT when all elements of array A have the same value will be equivalent to the worst case running of QUICKSORT **since no matter what pivot is picked,** QUICKSORT will have to go through all the values in A. And since all values are the same, each recursive call will lead to unbalanced partitioning.

Thus the recurrence will be:

T(n)=T(n−1)+Θ(n)

T(n)=Θ(n2)