Problem:
Let $ 0< \alpha <.5 $ be some constant. Consider running the Partition subroutine on an array with no duplicate elements and with the pivot element chosen uniformly at random (as in QuickSort and RSelect). What is the probability that, after partitioning, both subarrays (elements to the left of the pivot, and elements to the right of the pivot) have size at least $ \alpha $ times that of the original array?
Solution:
It is easiest to look at problem of this sort in term of concrete numbers, it is very easy that way, let say $ \alpha = 0.2 $ and $ n = 10 $. Then the requirement is that we have at least 2 elements in both subarrays. Further suppose the numbers are simply $ 1,2,\cdots, 10 $, then as long as we are not picking 1, 2, 9, 10, we are good to go.
Generalizing, it is easy to see that if we are not picking the $ n\alpha $ largest numbers and $ n\alpha $ smallest numbers, then we satisfy the condition, the probability of that is simply $ 1 - 2\alpha $.
Let $ 0< \alpha <.5 $ be some constant. Consider running the Partition subroutine on an array with no duplicate elements and with the pivot element chosen uniformly at random (as in QuickSort and RSelect). What is the probability that, after partitioning, both subarrays (elements to the left of the pivot, and elements to the right of the pivot) have size at least $ \alpha $ times that of the original array?
Solution:
It is easiest to look at problem of this sort in term of concrete numbers, it is very easy that way, let say $ \alpha = 0.2 $ and $ n = 10 $. Then the requirement is that we have at least 2 elements in both subarrays. Further suppose the numbers are simply $ 1,2,\cdots, 10 $, then as long as we are not picking 1, 2, 9, 10, we are good to go.
Generalizing, it is easy to see that if we are not picking the $ n\alpha $ largest numbers and $ n\alpha $ smallest numbers, then we satisfy the condition, the probability of that is simply $ 1 - 2\alpha $.
No comments:
Post a Comment