The Gateway to Computer Science Excellence
+3 votes
Let $0<α<.5$ be some constant (independent of the input array length $n$). 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?

1. $1 - 2*\alpha$

2. $\alpha$

3. $1 - \alpha$

4. $2 - 2*\alpha$
in Algorithms by
retagged by | 295 views

1 Answer

+2 votes
Best answer
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.
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,314 questions
60,435 answers
95,251 users