In randomized Selection, the element used to partition is called a pivot.
Given n elements, define a pivot as balanced if each side of the partition ends up with at least a constant fraction (1 / c )* n of the input. Otherwise, a pivot is called unbalanced. In both cases, the partition takes d*n time.
Suppose that when we run the algorithm, every balanced pivot is followed by u unbalanced pivots, where u is a constant.
Following a similar example in the course notes, show this under the above conditions, the algorithm will take O(n) time in the worst case. As always for upper bounds, exaggerate and simplify.
Hi there! Click one of our representatives below and we will get back to you as soon as possible.