GATE CS 2019 Q20 — Searching, Sorting, Hashing

In Quicksort, the worst-case partitioning occurs when the pivot splits the array of size $n$ into two highly unbalanced subproblems of sizes $0$ and $n-1$.

This worst-case scenario happens when the chosen pivot is either:

1. The minimum element of the array (placed at the leftmost position after partitioning).
2. The maximum element of the array (placed at the rightmost position after partitioning).

For an array of $n = 25$ distinct elements:

• Total number of possible pivot choices = $25$
• Number of choices leading to the worst-case partition = $2$ (the minimum and the maximum elements)

Since the pivot is chosen uniformly at random, the probability $P$ of selecting a worst-case pivot is: