0
$\begingroup$

Background

Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm:

Quicksort($a$):

  • (1) If length($a$) $> 1$, then
  • 1.1) pivot $← a [1]$.
  • 1.2) less $← a[a <$ pivot].
  • 1.3) equals $← a[a ==$ pivot].
  • 1.4) greater $← a[a >$ pivot].
  • 1.5) $a ←$ concat(Quicksort(less), equals, Quicksort(greater)).
  • (2) Output $a$.

It is clear to see that the total number of comparisons will follow the recurrence equation:

$$C(n) = C(n-1) + (n-1) \space \space \text{ where } \space C(2) = 1$$

From here we see that $C(n) = \Theta (n^2)$

Here is the context under which this came up:

enter image description here

Question

The above is clear to me, however, I have now read that if we use the median as a pivot (which can be identified in $\Theta (n)$ time), then we get the following recurrence inequality:

$$ C(n) \leq 2C ( \lceil n/2 \rceil -1) + Mn $$

And this gives the result that $C(n) = \Theta (n \log n)$.


How have these two results been derived (the recurrence inequality and time complexity for the updated algorithm)? The only difference is that we are computing the median each time. This is achieved in $\Theta (n)$ time each time that it is calculated but it still isn't entirely clear where this inequality comes from or why the new time complexity is $\Theta(n \log n)$ for the entire algorithm.


Here is the exact context under which it came up:

enter image description here

$\endgroup$
8
  • $\begingroup$ (Output $a$ in each recursive call?) $\endgroup$
    – greybeard
    Commented May 13, 2023 at 9:23
  • $\begingroup$ For $C(n) = \frac{n(n-1)}{2}$, we have $0.5 n^2 \leq C(n) \leq n^2$ for some $n \ge n_0$ @greybeard $\endgroup$
    – FD_bfa
    Commented May 13, 2023 at 9:55
  • $\begingroup$ Does this not suggest that $C(n) \in O(n^2)$ and $C(n) \in \Omega (n^2)$? And if it is both, then that means $C(n) \in \Theta (n^2)$ as suggested in the post @greybeard $\endgroup$
    – FD_bfa
    Commented May 13, 2023 at 9:57
  • $\begingroup$ Yes. They may be smaller (many items equal to pivot). Another reason not to be happy with theta… $\endgroup$
    – greybeard
    Commented May 13, 2023 at 10:22
  • $\begingroup$ If we are only looking for a formula for the worst case run time, then I think we should assume that there are no items equal to the pivot @greybeard $\endgroup$
    – FD_bfa
    Commented May 13, 2023 at 10:23

1 Answer 1

2
$\begingroup$

The genuine Quicksort is an in-place algorithm, and your version with concatenations uses extra memory and is much less efficient for this reason [$\Theta(n^2)$ instead of $O(n^2)$ with best case $O(n\log n)$]. Also, it is a waste of time to apply the trichotomy <, =, >, which costs two comparisons where you can do with a single.

This said, the behavior of Quicksort relies on the "balancing" of the pivot: it every pivot generates a partition with a single element on a side and the rest on the other side, the total complexity is indeed proportional to $n+(n-1)+(n-2)+\cdots $, which is $\Theta(n^2)$.

But if every pivot splits the array in two equal halves, the total complexity is like $n+\dfrac n2+\dfrac n2+\dfrac n4+\dfrac n4+\dfrac n4+\dfrac n4+\cdots$, which equals $n\log_2n$.


Note that Quicksort is never implemented with the median taken as the pivot, because the linear-time median algorithm is complicated and much slower than the partitioning process itself. If one needs an algorithm with guaranteed worst-case complexity $O(n\log n)$, Heapsort is a better choice.

$\endgroup$
8
  • $\begingroup$ @greybeard: the first paragraph does not assume a median pivot. Just a plea against this version. $\endgroup$
    – user16034
    Commented May 13, 2023 at 16:36
  • $\begingroup$ (I hope not: Θ(n²) effort for all slices/copies combined, not for a single one.) $\endgroup$
    – greybeard
    Commented May 13, 2023 at 16:38
  • $\begingroup$ Thank you for this answer. That clarifies the second part of my question. I’m still unsure about where the recurrence inequality comes from though $\endgroup$
    – FD_bfa
    Commented May 13, 2023 at 16:59
  • $\begingroup$ @FD_bfa: simply from "to sort $n$ elements, partition the array in two halves and sort them separately". $\endgroup$
    – user16034
    Commented May 13, 2023 at 17:01
  • $\begingroup$ My understanding is that $Mn$ is the number of comparisons needed to find the median and $2C( \lceil n/2 \rceil )$ accounts for the number of comparisons after we have split the array in half. But this doesn’t seem to include the $n-1$ comparisons with the pivot in order to assign each element to one of the 2 arrays $\endgroup$
    – FD_bfa
    Commented May 13, 2023 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.