Does one level of worst-case recursion in quicksort cost $\Theta(n^2)$ or $\Theta(n)$?

Question

Page 180 (section 7.4.1) of CLRS 3rd edition says

a worst-case split at every level of recursion in quicksort produces a $\Theta(n^2)$ running time

It seems that $\Theta(n^2)$ should be $\Theta(n)$ since lines 5~6 of the PARTITION procedure run n times at most.

Is my understanding correct?

Answer 1

We saw in Section 7.2 that a worst-case split at every level of recursion in quicksort produces a $\Theta(n^2)$ running time, ...

The original statement starts with "we saw in section 7.2". Section 7.2 contains the following, which explains the statement above in detail.

Worst-case partitioning

The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with $n-1$ elements and one with $0$ elements... Let us assume that this unbalanced partitioning arises in each recursive call. The partitioning costs $\Theta(n)$ time. Since the recursive call on an array of size $0$ just returns, $T(0)=T(1)$, and the recurrence for the running time is

$ T(n) = T(n-1) + T(0) + \Theta(n)$
$ \phantom{ T(n) }=T(n-1) + \Theta(n).$

Intuitively, if we sum the costs incurred at each level of the recursion, we get an arithmetic series (equation (A.2)), which evaluates to $\Theta(n^2)$. Indeed, it is straightforward to use the substitution method to prove that the recurrence $ T(n) = T(n-1) + \Theta(n)$ has the solution $T(n)=\Theta(n^2)$. (See Exercise 7.2-1.) Thus, if the partitioning is maximally unbalanced at every recursive level of the algorithm, the running time is $\Theta(n^2)$.

Basically, as you have observed, any partitioning of an $m$-element (sub)array costs $\Theta(m)$ time, with any split, whether in worst-case or not. With "a worst-case split at every level of recursion", the quicksort partitions an array of $n$ elements, then a subarray of $n-1$ elements, then a subarray of $n-2$ elements, and so on until a subarray of 1 element at last. If we sum the costs incurred at every level of the recursion, we see the total running time is $\Theta(n^2)$.

Put in another way, "a worst-case split at every level" means "worst-case splits at all levels".

It is a standard convention to describe "all" items by "every" item.

"A worst-case split at every level of recursion in quicksort" here should be understood as "Running quicksort that splits at every level of recursion in the worst way", instead of "Running one level of recursion in quicksort" with "a worst-case split".

---

Does one level of worst-case recursion in quicksort cost $\Theta(n^2)$ or $\Theta(n)$?

For quicksort that runs with a worst-case split at every level of recursion,

• the first level runs in $\Theta(n)$-time,
• the second level runs in $\Theta(n-1)$-time,
• the third level runs in $\Theta(n-2)$-time,
• ...
• the last level runs in $\Theta(1)$-time.

The $k$-th level runs in $\Theta(n-k+1)$ time.