Exercise 7.2.3
Show that the running time of
QUICKSORT
is when the array contains distict elements and is sorted in decreasing order.
In this case PARTITION
always returns because all the elements are
greater than the pivot. While the if will never be executed, we still get
one empty partition and the recurrence is (even if
its body is not executed, the for is still ).