6.11

Let the elements be distinct and indexed 1 … n in sorted order, so choosing a pivot uniformly at random is equivalent to choosing its rank R uniformly from {1, 2, …, n}. Both resulting sub-arrays have size at least αn iff the pivot’s rank lies in the middle interval
[math]\displaystyle{\alpha n \le R-1\le (1-\alpha)n\; \Longleftrightarrow\; \alpha n < R < (1-\alpha)n.}[/math]
That interval contains (1−2α)n positions (up to a ±1 rounding error that vanishes as n grows).
Because each rank is chosen with probability 1/n,
[math]\displaystyle{\Pr\bigl[\text{balanced split}\bigr] = \frac{(1-2\alpha)n}{n} = 1-2\alpha.}[/math]
Thus the probability that a uniformly random pivot gives two subproblems of size at least αn is
[math]\boxed{\,1-2\alpha\,}.[/math]

Back to Chapter 6