# Probabilty that quicksort partition creates an imbalanced partition

I have come across this question:

Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is ≥α times the size of the original array?

Can anyone explain me how has this answer come?

• What have you tried and where did you get stuck? Hint: try to figure out the probability that the pivot has rank $k$. – Raphael Aug 25 '14 at 12:34

If $\alpha=0.5$, then $1-2 * 0.5 = 0$, which says that the smaller subarray cannot have length greater than half the original, since then it would be the larger subarray.

If $\alpha=0$, then $1-2 * 0 = 1$, so the size of any subarray must be greater than or equal to zero.

The pivot is randomly chosen, so uniformly distributed between $0$ and $1$. The probability that a particular subarray has size $\geq a = 1-a$. Probability that that particular subarray is also less than half the size of the original $= 0.5-\alpha$. If you're talking about not a particular subarray but whichever one is the smallest, then double it, meaning it has probability $1.0$ of being between $0$ and $0.5$ the length of the original. That is $p=1-2\alpha$.

That explanation makes intuitive sense to me. Basically the answer just says the size of the smaller subarray is uniformly distributed between $0$ and $0.5$ the size of the original.

The other answers didn't quite click with me so here's another take:

If at least one of the 2 subarrays must be you can deduce that the pivot must also be in position . This is obvious by contradiction. If the pivot is then there is a subarray smaller than . By the same reasoning the pivot must also be . Any larger value for the pivot will yield a smaller subarray than on the "right hand side".

This means that , as shown by the diagram below:

What we want to calculate then is the probability of that event (call it A) i.e .

The way we calculate the probability of an event is to sum of the probability of the constituent outcomes i.e. that the pivot lands at .

That sum is expressed as:

Which easily simplifies to:

With some cancellation we get: