[Solved]: Probabilty that quicksort partition creates an imbalanced partition

Problem Detail: 

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?

The answer is 1-2*α.

Can anyone explain me how has this answer come?

Asked By : POOJA GUPTA

Answered By : Joseph Mark

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29369