GATE 2019 CS – Question 30
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 0.07 to 0.09
Explanation
The worst locations are the two ends (the pivot is the smallest or the largest element), so the probability is $\frac{2}{25}=0.08$.