Question

An array of 25 distinct elements is to be sorted using quicksort. 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 __________

Hint:

In quicksort with random pivot selection, worst-case partitioning occurs only when the pivot is the minimum or maximum element. So, probability of worst case in the first partition is always $\dfrac{2}{n}$ for an array of $n$ distinct elements.

Answer 1

Correct Answer: 0.08

Step 1: Recall when quicksort performs worst. 
In quicksort, the worst-case situation arises when the chosen pivot ends up at an extreme end of the array after partitioning.
This happens when the pivot is either the smallest or the largest element, producing one subarray of size $n-1$ and another of size zero.

Step 2: Identify the unfavorable pivot choices.
The array contains 25 distinct elements, and the pivot is selected uniformly at random.
Only two elements can lead to the worst-case split:

• the smallest element
• the largest element

 

Thus, the number of unfavorable pivot choices is 2.

Step 3: Compute the probability.
Since each of the 25 elements is equally likely to be chosen as the pivot, the probability of selecting a worst-case pivot in the first partition is:

\[ \text{Probability} = \frac{2}{25} = 0.08 \]

Step 4: Final answer.
The computed probability is already expressed to two decimal places.

\[ \boxed{0.08} \]