In randomized Selection, the element used to partition is called a pivot.

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.