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?

  • 1
    $\begingroup$ What have you tried and where did you get stuck? Hint: try to figure out the probability that the pivot has rank $k$. $\endgroup$ – 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 formula you can deduce that the pivot must also be in position formula. This is obvious by contradiction. If the pivot is formula then there is a subarray smaller than formula. By the same reasoning the pivot must also be formula. Any larger value for the pivot will yield a smaller subarray than formula on the "right hand side".

This means that formula, as shown by the diagram below:

enter image description here

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

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 formula.

That sum is expressed as:

enter image description here

Which easily simplifies to:

enter image description here

With some cancellation we get:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.