Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Let 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 ≥α times the size of the original array?
- 1−α
- α
- 2−2∗α
- 1−2∗α
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement