# Analyze SELECT to show that if n 140, then at least dn=4e elements are greater than the…

Analyze SELECT to show that if n 140, then at least dn=4e elements are greater than the median-of-medians x and at least dn=4e elements are less than x. Show how quicksort can be made to run in O.n lg n/ time in the worst case, assuming that all elements are distinct.