# 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:

Lets try to understand it with Example

say size of Array n = 4. and the constant i.e. size of smaller sub array out of sub arrays(small,large) after split by Pivot is within range 0<α<.5 of the size of original array which means 0< α < 2(in short α = 1) in this case.

in any case if smaller sub array will touch boundaries it will not remain smaller sub array any more(i.e. if α = 0,2).

now this α will be there twice, as pivot will move and will split the array e.g 1,2,3,4

pivot: 2 smaller sub array size: 1 (i.e.1) ;pivot: 3 smaller sub array size: 1 (i.e.4)

now size of smaller sub array will be:

(array size - small sub array size)(*this is large sub array)-(small sub array size)

Lets check : 4 - 2*1 = 2.

so the probability of size of smaller sub array to that original array in this case = 2/4 = 1/2. which is (n - 2*n*α)/n = (1-2α).

• I find this rather hard to follow. Also, trying to derive a formula from a single small example is a bad idea -- how do you know your formula is right? And we can't have $\alpha=0.2$ if the array has size $4$. – David Richerby Oct 4 '17 at 9:30
• Example explained above is to check "Proof of Correctness" of that Probability (1-2α). For sure an Example can never be derived to Formulate Something and in this case Its (α = 0 comma 2) for Array of Size 4. – Vishal Patwardhan Oct 4 '17 at 11:59