Show that the running time of \(\textsc{Quicksort}\) is \(\Theta(n^2)\) when the array \(A\) contains distinct elements and is sorted in decreasing order.
When the array is sorted in decreasing order, quicksort’s standard partitioning creates maximally unbalanced splits at every level of recursion, leading to quadratic running time.
Consider an array sorted in decreasing order, say \(\langle 10, 8, 6, 4, 2 \rangle\). The \(\textsc{Partition}\) procedure selects the last element as the pivot. In this case, the pivot 2 is the smallest element in the array.
During partitioning, we compare each element \(A[j]\) with the pivot \(x = 2\). Since the array is in decreasing order and all elements before position \(r\) are greater than 2, every comparison \(A[j] \leq x\) evaluates to false. The index \(i\) remains at \(p - 1\) throughout the entire loop, and no swaps occur within the loop.
After the loop completes, the final swap in line 7 exchanges \(A[i+1] = A[p]\) with \(A[r]\). This places the pivot at position \(p\) and returns \(q = p\), creating two subarrays:
- Left subarray \(A[p..q-1]\): empty (size 0)
- Right subarray \(A[q+1..r]\): contains \(n-1\) elements
The right subarray \(A[p+1..r]\) still contains elements in decreasing order (since we only moved the smallest element to the front). The same unbalanced partitioning repeats at each recursive level.
The recurrence relation is:
\[T(n) = T(0) + T(n-1) + \Theta(n) = T(n-1) + \Theta(n)\]This is the same recurrence that we solved in Excercise 7.2-1, which tells us it would be \(\Theta(n^2)\).