Problem:
Let $ 0 < \alpha < 0.5 $ be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. 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 $ \ge \alpha $ times the size of the original array?
Solution:
It is easy to think in terms of actual value for $ \alpha $ and $ n $, for example, $ n = 40 $ and $ \alpha = 0.25 $, then we need to make sure the pivot is chosen so that it is either larger than (or equal to) the 10th element or smaller than (or equal to) the 30th element, so we are clear in general how to reason about this.
Therefore, the answer is $ 1 - 2 \alpha $.
Let $ 0 < \alpha < 0.5 $ be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. 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 $ \ge \alpha $ times the size of the original array?
Solution:
It is easy to think in terms of actual value for $ \alpha $ and $ n $, for example, $ n = 40 $ and $ \alpha = 0.25 $, then we need to make sure the pivot is chosen so that it is either larger than (or equal to) the 10th element or smaller than (or equal to) the 30th element, so we are clear in general how to reason about this.
Therefore, the answer is $ 1 - 2 \alpha $.
Andrew,
ReplyDeletei banged my head to solve this question, do you have a theoritical explanation to arrive at the probablity ?
i would love that !