Quick-sort (7)
In the worst case, the pivot turns out to be the smallest value. So the right subarray has length n–1 whilst the left subarray has length 0. Then step 1.3 performs comps(n–1) comparisons, but step 1.2 does nothing at all.
Therefore: comps(n) ? comps(n–1) + n – 1 if n > 1 comps(n) = 0 if n ? 1
Solution: comps(n) ? (n2 – n)/2
Worst-case time complexity is O(n2).
The worst case arises if the array is already sorted!