7.2-3

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

If the elements are sorted in decreasing order i will not increment from p-1 and for the lines 3-6 of the PARTITION procedure. The largest value in the array will be swapped with smallest elements and a partition of 0 and n -1 will be created. After the second iteration again a partition of 0 and n-2 will be created. This will continue until smaller partition of two elements is created. All the n-1,n-2.. elements will be iterated n-2,n-3.. times. This is an arithmetic progression hence the running time is $\theta(n^2)$.