Exercise 9.2.4
Suppose we use
RANDOMIZED-SELECT
to select the minimum element of the array . Describe a sequence of partitions that results in a worst-case performance ofRANDOMIZED-SELECT
.
This happens if all the elements get picked up in reverse order that is, the first pivot chosen is 9, the second is 8, the third is 7 and so on.