1
$\begingroup$

I know recurrence relation corresponding to quick sort worst case is

$T(n)=T(n-1)+T(0)+\Theta(n)$

and time complexity is $O(n^2)$.

This happens when we select pivot which is either largest element or smallest element in the current sub problem.

This can occur when array is sorted in either descending or ascending order and we select either largest or smallest element as pivot.

I also know that best case occurs when median is chosen as pivot, giving recurrence relation

$T(n)=T(n/2)+T(n/2)+\Theta(n)$.

and time complexity $O(n \log n)$.

Statement 1: Any other partition should result in average case.

I have come across problems each time choosing pivot which partition array in some fixed proportion (say $T(n)=T(n/10)+T(9n/10)+\Theta(n)$) ending in average case performance of $O(n \log n)$ (and I understand its proof).

However I have also came across text saying:

Statement 2: Any pivot which does not partition array in some proportion should result in worst case. If $n$th smallest or largest element is selected as pivot, it will result in worst case.

Q1. Is statement 1 true? If no, which other pivot selection strategies could result in worst case or best case behavior?

Q2. Is statement 2 true?

$\endgroup$

4 Answers 4

1
$\begingroup$

The time complexity for particular runs of quicksort can be anywhere between the best case and the worse case. It can be $\Theta(n(\log n)^2)$, $\Theta(n^{\frac32})$, $\Theta(n^{\frac{19}{10}})$ or $\Theta(n^2/\log n)$. Given any $f$ such that $n\log n\le f(n)\le n^2$, we can construct runs of quicksort whose time-complexity is $\Theta(f(n))$.

Let $q$ be a quicksort algorithm. Let $c_q(A)$ be the number of comparisons used by $q$ on input array $A$. Let $m_{q,n}=\min_{\#A=n}c_q(A)$ and $M_{q,n}=\max_{\#A=n}c_q(A)$ for $n>0$. The following property holds for various versions of quicksort.

Continuum of comparisons by quicksort: Given any integer $i$ between $m_{q,n}$ and $M_{q,n}$, there is an array $A$ of size $n$ such that $c_q(A)=i$.

We can replace "comparisons" above by "swaps".


Statement 1: Any other partition should result in average case.

Q1. Is statement 1 true? If no, which other pivot selection strategies could result in worst case or best case behavior?

The "continuum of comparisons by quicksort" shows statement 1 does not make much sense. To determine the asymptotic behavior of a quicksort algorithm, we need to specify the version of quicksort with its partition scheme and which kind of input arrays might be given. It does not make much sense to say $O(n\log n)$ is the time-complexity of the average case without specifying "the average case".

Instead of statement 1, here is the clearer summary, where the average case is when the given input arrays are uniformly random, as described here.

  • All quicksort algorithms (that I have seen, including these variants) takes $\Theta(n \log n)$ time in expectation in the average case.

  • Some quicksort algorithms choose the pivot that partition an array within some fixed proportion. Those algorithms run in $\Theta(n\log n)$-time in all cases, assuming a linear-time algorithm is used to choose the pivot. However, the constant factors hidden in the big $\Theta$-notations for these algorithms are much larger than those factors for other algorithms.


Statement 2: Any pivot which does not partition array in some proportion should result in worst case. If nth smallest or largest element is selected as pivot, it will result in worst case.

Q2. Is statement 2 true?

Although sounds reasonable, statement 2 is too ambiguous to be verified or refuted. The following is a version that could be proved.

Statement 3: The classic quicksort with Lomuto partition scheme or Hoare partition scheme runs in $\Theta(n^2)$-time if the pivoting on every array partition the array into two parts with one part of size $O(1)$. In particular, for any constant $c$, if $c$-th smallest or $c$-th largest element is selected as pivot whenever the size is no less than $c$, it runs in $\Theta(n^2)$ time.


Exercise 1. Prove statement 3.

Exercise 2. Prove "continuum of comparisons by quicksort" for a version of quicksort known to you.

$\endgroup$
4
  • $\begingroup$ Isnt statement 3 same as first recurrence relation I specified in question: $T(n)=T(n-1)+T(0)+\Theta(n)$? Statement 2 was specifically related to pivot being not dividing array in proportions. I understand there can be many possible time complexities and I need to explore more on that as you explained. But I was referring to time complexities given in most resources like this. Can you please comment on Draconis answer? Is he wrong? $\endgroup$
    – RajS
    Jan 13, 2019 at 18:50
  • $\begingroup$ Your statements as well as Draconis's answer are not precise enough to be labelled as correct or wrong. $\endgroup$
    – John L.
    Jul 16, 2019 at 14:07
  • $\begingroup$ Can you give an example of how a Quicksort case could be $\Theta(n^{3/2})$ ? $\endgroup$ Mar 10, 2022 at 20:21
  • $\begingroup$ @YvesDaoust Here is the full statement: there exists a sequence of arrays $A_1, A_2, A_3,\cdots, $ such that $f(n) = \Theta(n^{3/2})$, where $\#A_n$ is $n$ and $f(n)$ is the number of comparisons of quicksort with input $A_n$. The existence is guaranteed by the continuum of comparisons by quicksort mentioned in the answer, since the number of comparisons used by quicksort can be as small as $O(n\log n)$ and as big as $\Theta(n^2)$. Here quicksort refers to the simplest deterministic versions of quicksort. $\endgroup$
    – John L.
    Mar 10, 2022 at 20:44
0
$\begingroup$

One addition: Always picking the median element is not necessarily optimal. Quicksort spends time comparing items and time moving items. Picking the median element minimises the number of comparisons, but the number of moves is smaller if we don't pick exactly the median. Depending on the relative cost of comparing and moving items, picking a pivot a bit away from the median can be faster.

$\endgroup$
1
  • $\begingroup$ Picking the median or any other quantile does not come for free. It takes extra comparisons and moves. $\endgroup$ Mar 10, 2022 at 20:32
0
$\begingroup$

It is true that when all partitions fulfill a constant proportion (or better), the $n\log n$ behavior occurs. This is because the size of the partitions decreases in geometric progression.

In particular, the median-of-medians strategy ensures such a ratio.

It is also true that when no partition fulfills a constant proportion, the $n^2$ behavior occurs. This is because the size of the partitions decreases in arithmetic progression.

Statement 1 is wrong. (Unless part of the context is missing or "any other partition" has a special meaning.)

Statement 2 is right.

$\endgroup$
-1
$\begingroup$

Remember, for big-O we care about the asymptotic limit. If you choose the $k$th largest (or smallest) element, for constant $k$, then when you make $n$ big enough it's as though you chose the single largest or smallest. The $k$ elements on the other side just aren't enough to matter any more. So statement 2 is true.

Statement 1 is also true; you say you understand the proof of it, so I'm not sure how much detail to go into here. But intuitively, the amount on each side of the pivot grows proportionally to $n$. That's what makes it different from the constant $k$.

$\endgroup$
1
  • $\begingroup$ IMO, "other partition" does not mean $k^{\text{th}}$ largest. $\endgroup$ Mar 10, 2022 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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