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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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