When average , worst and best case time complexity happens in quick sort?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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$.