I'm reading Algorithms Illuminated: Part 1, and problem 5.2 states:
Let ɑ be some constant, independent of the input array length n, strictly between 0 and 1/2. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of both the resulting subproblems is at least ɑ times the size of the original array?
Answer choices are:
- ɑ
- 1 - ɑ
- 1 - 2ɑ
- 2 - 2ɑ
I'm not sure how to answer this question. Any ideas?
Let there be N elements in the array. If the picked pivot is one of the smallest [Nα] elements in the array, then the left partition's size will be less than Nα. Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than Nα.
Hence, there are N - 2 * [Nα] elements that you can pick such that both partitions have size greater than or equal to Nα. Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked.
So, the probability of getting such a split is 1 - 2α + O(1 / N).
