Take an example α = 0.3 and the array be
A = {1,2,3,4,5,6,7,8,9,10}
So,according to the given question we have to choose pivot from the array A in such a way that the length of the smaller array after calling PARTITION subroutine would be >= (3/10) * 10 = 3
Now, the number of ways we can select a pivot from the array A = 10 (length of the array A)
So, the cardinality of the sample space = 10
Now, observe that if we choose a pivot from the numbers {4,5,6,7} then only the length of the smaller sub array would be greater than 3.
So, the cardinality of the event space = 4
Hence the probability = 4/10 = 2/5.
Now, put α = 3/10 in the given options
Option 1 : 1-2*(3/10) = 4/10 = 2/5
Option 2 : 3/10
Option 3 : 1-(3/10) = 7/10
Option 4 : 2 - 2*(3/10) = 7/5
So, we get that only Option 1 matches with our answer in the example.
Hence correct answer is option 1.
Now, generalize the problem
Take an arbitrary array { a1,a2,a3,.........,an }
The number of elements which can be chosen as pivot from the above array is n (length of the sub array)
So, the sample space = n
Now suppose we choose the mth smallest element in that array am (say) as pivot
Then the length of the left subarray = m-1 and the length of the right subarray = n-m-1
Note that according the problem the length of the two sub arrays must be >= α*n
So, we can choose only from (α*n +1)th smallest element to (n-α*n)th smallest element as pivot.
So, the number of elements we can choose as pivot is (n - 2 α*n)
So, the event space = (n - 2 α*n)
Thus the probability = (n - 2 α *n) / n = 1- 2 α (Answer)
Hence option A is the correct answer.
