Question

An array of 25 distinct elements is to be sorted using quick sort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.

Answer 1

Since the given array is sorted

Let given array be 1, 2, 3, 4, 5, 6, 7, …. 25

Probability of choosing each element is \(\frac{1}{25}\)

Worst case for quick sort will only we arise if 1 is chosen or 25 is chosen as pivot element

Assume 1 is chosen as a pivot element

After first round of partitioning, pivot will be in its same position (1^st position), this gives rise to worst case in quick sort since the complexity will be O(n²).

Assume 25 is chosen as a pivot element

After first round of partitioning, pivot will be in its same position (last position), this gives rise to worst case, in quick sort since the complexity will be O(n²).

P(X = 1) = \(\frac{1}{25}\) = 0.04

and P(X = 50) = \(\frac{1}{25}\) = 0.04

P(X = 1 or X = 25)

= 0.04 + 0.04

= 0.08