Let 0 < a < 0.5 be some constant. We have an n-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With which probability the smallest section be greater than an. my short answer in note say with probability 1-2a. anyone could say how this probability calculated?
The size of the smaller partition is evenly distributed in the range [0, n/2], so the probability that it will be smaller than an is an / (n/2). So the probability that it will be larger than a is 1 - an / (n/2). an/(n/2) is precisely 2a, hence the probability 1 - 2a.
Here's a diagram, in case it helps:
Pivot positions
a·n n/2 a·n+n/2 n
v v v v
<---------------------|||||||·---------------------|||||||>
/---^---\ /---^---\
smaller partition on left smaller partition on right
bigger than a·n bigger than a·n
size: n/2 - a·n size: n - (a·n + n/2)
Total size: n - 2a·n
Probability: 1 - 2a
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments