in Algorithms recategorized by
737 views
2 votes
2 votes
probability of a split more balanced than a to (1-a) split in partitioning procedure of quicksort where 0<a<=1/2?

1-3a        1-2a     a+1        none
in Algorithms recategorized by
737 views

1 Answer

2 votes
2 votes

I believe $\left ( 1 - 2a \right )$ should be the right answer.

Partition will divide original array into two sub arrays.

I am using a random variable $X$ to denote the fractional length of smaller partition of the original array with respect to the length of original array.

Consequently, the fractional length of the larger partition will be $\left ( 1 - X \right )$ with respect to the length of original array.

For example suppose, $X = 0.2$ then it will indicate  that  our smaller sub array (among the two sub arrays that we got after partitioning) is $0.2$ time the original array.

and hence the larger sub array is $\left ( 1 - 0.2 \right )$ or $0.8$ times the original array.

Since $X$ is denoting the fractional length of smaller sub array after partition, its value can not exceed more than $0.5$ times the original array otherwise it will no longer be the smaller sub array.

Hence the domain of random variable $X$ is $\left ( 0, \frac{1}{2} \right ]$, that is $X$ can take any values between $0$ and $\frac{1}{2}$.

 It can be inferred that as $X$ approaches to $\frac{1}{2}$, $\left ( 1 - X \right )$ also approaches to $\frac{1}{2}$, that is the sizes of two sub arrays are being equal or in other words the partition becomes more balanced.

$X = \frac{1}{2}$ means we have got two sub arrays of equal size,and both of them are $0.5$ times the original array, this is the most desirable situation from the efficiency's point of view.

As $X$ approaches to $0$, the partition becomes more unbalanced.


Now if we want a split more balanced than $a\mid \left ( 1 - a \right )$ where $a\ \epsilon \left ( 0, \frac{1}{2} \right ]$, we have to set our random variable $X's$ value larger than $a$, so that our random variable is more nearer to $\frac{1}{2}$ , then the $a$ is (as a value nearer to $\frac{1}{2}$ implies a more balanced partition).

So to get a partition more balanced than $a\mid \left ( 1 - a \right )$, $X$ must lie in the range $\left ( a, \frac{1}{2} \right ]$.

Hence the probability of getting a more balanced split than $a\mid \left ( 1 - a \right )$ is same as $P\left ( X > a \right )$,

And $P\left ( X > a \right ) = \frac{\text{length of favourable domain of X}}{\text{length of complete domain of X}}$.

$\Rightarrow P\left ( X > a \right ) = \frac{\left ( \frac{1}{2} - a \right )}{\left ( \frac{1}{2} - 0 \right )}$

$\Rightarrow P\left ( X > a \right ) = \left ( 1 - 2a \right )$.

It can also be observed that using the above formula when $a$ becomes $ \frac{1}{2} $ there is $0$ probability of getting a more balanced split, and when $a$ tends to $0$, there is almost full probability of getting a more balanced split.

So derived formula for probability is consistent with our intuition.

edited by

3 Comments

Thanx for the comprehensive explanation..
1
1

I understood the entire explanation ,just confusion in the last statements , you said that as a=1/2 when a becomes 12 there is  zero0probability of getting a more balanced split, and when aa tends to 0zero , there is almost full probability of getting a more balanced split.

when a=1/2 implies that we have a split exactly in the middle then how come probability is zero and as a approaches towards zero we may have a possibility of unbalanced split .

0
0

When $a$ becomes $\frac{1}{2}$ there is $0$ probability of getting a more balanced split, and when $a$ tends to $0$, there is almost full probability of getting a more balanced split.

Here, I mean that when $a$ becomes $\frac{1}{2}$, it divides the array into $2$ partitions of exactly same size, so it is already splitting the array in the most balanced way.Thus no matter what value we choose for our random variable $X$,we are never going to achieve a split which is more balanced than $\frac{1}{2} \mid \frac{1}{2}$.

So Probability of getting a more balanced split than $a$ will be $0$.

Similarly, when $a$ tends to $0$ it will split the array in the most unbalanced way, so no matter what value we choose for our random variable $X$, we are  almost always guaranteed to get a more balanced split then $0 \mid 1$.

0
0

Related questions