Probability based on quicksort section

Question

I came across this question:

Let 0 <α <5 be some constant (regardless of the length of the input array n). Recall the section routine used by the QuickSort algorithm, as explained in the lecture. What is the likelihood that with a randomly selected reference element, the Partition subroutine produces a partition in which the size of the smaller of the two subarrays is ≥α times the size of the original array?

Its answer is 1-2*α. 

Can someone explain to me how this answer came? Please, help.

Answer 1

The choice of the rotary element is random, with a uniform distribution.

There are N elements in the array, and we will assume that N is large (or we won’t get the desired answer).

If 0≤α≤1, the probability that the number of elements smaller than the axis is less than αN is equal to α. The probability that the number of elements greater than the axis is less than αN will be the same. If α≤ 1/2, then these two possibilities are exceptional.

To say that a smaller subarabar has a length ≥αN is that none of these conditions is satisfied, so the probability is 1-2α.

Answer 2

The length of the array is n. For a shorter length, the array> = αn pivot should be greater than the number nn. At the same time, the pivot point should be less than αn the number of elements (a smaller array size will be less than required)

So, from the n element, we must choose one of the (n-2α) n elements.

the required probability is n (1-2α) / n.

Therefore, 1-2α

Answer 3

The probability will be the number of desired elements / total number of elements. In this case ((1-αn) - (αn)) / n Since α lies between 0 and 0.5, (1-α) must be greater than α. The number of elements contained between them will be, (1-α-α) p = (1-2α) p and, thus, the probability would be, (1-2α) p / p = 1-2α

Answer 4

Another approach to solving the problem (for those who have a difficult understanding of time, like me).

Firstly. Since we are talking about the “smaller of the two subarrays,” its length is less than 1/2 * n (n is the number of elements in the original array).

Second. If 0 <a <0.5 means that a * n is less than 1/2 * n. And therefore, we are now talking about two randomly selected integers, limited to 0 for the smallest and 1/2 * n for the highest.

Thirdly. Let's imagine the bones with numbers from 1 to 6 on the sides. Allows you to select a number from 1 to 6, for example 4. Now roll the bones. Each number has a probability of 1/6 to be the result of this throw. Thus, for the case "the result is less than or equal to 4", we have a probability equal to the sum of the probabilities of each of these results. And we have numbers 1, 2, 3 and 4. In total p (x <= 4) = 4 * 1/6 = 4/6 = 2/3. Thus, the probability of an event exceeding 4 is p (x> 4) = 1 - p (x <= 4) = 1 - 2/3 = 1/3.

Fourth. Let's get back to our problem. "Selected Number" is now * n. And we are going to throw a cube with numbers from 0 to (1/2 * n) on it to get k - the number of elements in the smallest of the subarrays. The probability that the result will be limited (a * n) at the maximum is equal to the sum of the probabilities of all outcomes from 0 to (a * n). The probability of any particular result k is p (k) = 1 / (1/2 * n).

Therefore, p (k <= a * n) = (a * n) * (1 / (1/2 * n)) = 2 * a.

From this we can easily conclude that p (k> a * n) = 1 - p (k <= a * n) = 1 - 2 * a.