# Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?

If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get worst-case performance regardless of whether your 'already sorted' list is in ascending or descending order?

My thinking is that, if you always choose the smallest element for your pivot, then whether your 'already-sorted' input is sorted by ascending or descending doesn't matter because the subset chosen to be sorted relative to your pivot will always be the same size?

• Your thinking is correct, but you can also argue directly and calculate the running time of quicksort in this case - you'll get $O(n^2)$. Commented Aug 31, 2012 at 5:28

## 3 Answers

The worst case complexity for quicksort is $\Theta(n^2)$. This is achieved by picking pivots that divide the set such that one group has only a single member. With a bad pivot picking algorithm, this can easily be achieved by picking one end of a sorted set. Your assumption is correct.

• It was better to write it: "... This is achieved by picking pivots that divide the set such that one group has only O(1) member"
– user742
Commented Aug 31, 2012 at 12:51
• @Saeed Amiri: That's right, but it's better to be precise.
– MMS
Commented Aug 31, 2012 at 19:13
• @SaeedAmiri: O(1) indicates that it is proportional to 1, which means it can be k*1. The actual worst case is achieved when it is exactly 1. I will grant you that O(1) may still lead to O(n^2). Commented Sep 1, 2012 at 0:07
• @MMS, I wrote $O(1)$ to be precise, walrii You wrote:"The worst case complexity for quicksort is $\Theta (n^2)$ ..", but in fact the only way to achieve $\Theta(n^2)$ is not the way you said, yes the way you described is worst case in all, but not the only $\Theta (n^2)$.
– user742
Commented Sep 1, 2012 at 8:53

Yes! You're thinking is absolutely right! And as correctly mentioned by Yuval Filmus, the running time will be $\Theta(n^2)$

One subarray will have $0$ or $1$ element while the other will have $(n-1)$ elements; hence it is $O(n^2)$: $$t(n)=t(n-1)+t(0)+O(n)= O(n^2)$$