-2
$\begingroup$

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?

$\endgroup$
  • 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
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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α).

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – David Richerby Oct 4 '17 at 9:30
  • $\begingroup$ 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. $\endgroup$ – Vishal Patwardhan Oct 4 '17 at 11:59

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.