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

This is another expression of the worst-case scenario of QUICKSORT. The pivot element selected from this array will always be less than all other elements and so we will partition the remaining elements such that one partition is empty. By partitioning the elements in this way, we get a recurrence of the form described in Exercise 7.2-1 which runs in \(\Theta(n^2)\) time.