2
$\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$
0
$\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$
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$
0
$\begingroup$

When we talk about best-case or worse-case or average-case time-complexity of quicksort (or just about any algorithm), the case of average case is very different from the best case or the worse case. The time-complexity $T(n)$ of average case is the average time-complexity of quicksort running on a (usually uniform) distribution of arrays of size $n$. While we can say a particular input is the best case or the worst case for some quicksort algorithm, we cannot just point to one particular input and say that input is the average case (even an average case) for some quicksort algorithm even though people do that sloppily all the time.


There are more than three cases if we consider different input for classical quicksort (with Hoare partition scheme ). The possible time complexity for particular runs of quicksort can be anywhere between the best case and the worse case. For example, it could be about $\Theta(n(\log n)^2)$ or $\Theta(n^{\frac32})$ or $\Theta(n^{\frac{19}{10}})$ or $\Theta(n^2/\log n)$. More specifically, given any $f(n)$ such that $\log n\le f(n)\le n$ for all $n$, we could construct runs of quicksort on an array of size $n$ whose time-complexity is $\Theta(nf(n))$. In fact, we have the following property of quicksort.

(Continuum of comparisons by quicksort) Let $c(A)$ be the number of comparisons used by the classic quicksort on array $A$. Let $m_n=\min_{\#A=n}c(A)$ and $M_n=\max_{\#A=n}c(A)$ for integer $n>0$. Given any integer $i$ such that $m_n\le i\le M_n$, there is an array $A$ of size $n$ such that $c(A)=i$.

This property holds for number of swaps and for many other quicksort algorithms as well. This property should help us understand the general picture of time-complexity of the classic quicksort.


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?

As analyzed in the previously paragraphs, statement 1 does not make much sense in the standard semantic. To determine the asymptotic behavior of a quicksort algorithm, we need to specifies both the actual kind of quicksort algorithm especially its partition scheme and which one of the best case, or worst case, or average case the input array will be. It does not make sense to say $O(n\log n)$ is the average case.

I would rather summarize the situation instead as the following.

  • All quicksort algorithms (that I have seen, including the variants here excluding the "non-pure" ones) is $\Theta(n\log n)$ in average case, that is, if the given input arrays are uniformly random. ( No precise definition of "uniformly random" is given here. It can be formulated rigorously, for example here.)

  • On the other hand, some quicksort algorithm (almost) always choose pivot that partition array in some fixed proportion. Those algorithms have $\Theta(n\log n)$ even in the worst cases of inputs. However, those algorithms usually have much larger constant factor hidden in the big $\Theta$-notation than the constant factor hidden in the big $\Theta$-notation of other algorithms in average case.


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?

"Any pivot which does not partition array in some proportion should result in worst case" sounds reasonable but not precise enough to be verified or refuted mathematically. The following is a precise version that can be proved.

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


The following two exercise may not be easy. Beginners should attempt them later.

Exercise 1. Prove statement 3.

Exercise 2. Prove the claim of "continuum of comparisons by quicksort".


The following two resources are not exactly about pure quicksort, but are related and interesting enough.

$\endgroup$
  • $\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$ – anir Jan 13 at 18:50
  • $\begingroup$ Please tell me if and where my updated answer have not answered all your questions, $\endgroup$ – Apass.Jack Jan 14 at 5:15

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.