1
$\begingroup$

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.

enter image description here

Is my understanding correct?

$\endgroup$
4
  • 1
    $\begingroup$ The recursion itself is O(n). Inside lies another O(n) (the partition function). Multiply them and you’ll get O(n^2) $\endgroup$
    – GreekMustard
    Commented Aug 4, 2022 at 23:33
  • $\begingroup$ They are saying that Partition is O(n) and Quicksort is O(n^2). $\endgroup$
    – DanielV
    Commented Aug 5, 2022 at 2:17
  • $\begingroup$ @GreekMustard thank you. Are we talking the same thing, "a worst-case split at every level", one level rather than the whole algorithm? $\endgroup$
    – JJJohn
    Commented Aug 5, 2022 at 3:28
  • $\begingroup$ @DanielV thank you. Are we talking the same thing, "a worst-case split at every level", one level rather than the whole algorithm? $\endgroup$
    – JJJohn
    Commented Aug 5, 2022 at 3:28

1 Answer 1

Reset to default
1
+50
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .