Exercise 7.2.3

Show that the running time of QUICKSORT is Θ(n2)\Theta(n^2) when the array AA contains distict elements and is sorted in decreasing order.

In this case PARTITION always returns pp 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 T(n)=T(n1)+Θ(n)T(n) = T(n-1) + \Theta(n) (even if its body is not executed, the for is still Θ(n)\Theta(n)).