What is the worst-case cost for Quicksort to sort an array of n elements?
\Theta(n^2)\Theta(n)\Theta(\log n)\Theta(n \log n)There are a few really bad inputs.
The bad cases have pivots that repeatedly reduce the partition size by one.
That leads to a series of partition sizes of
n-1, n-2>, and so on.
Since the time to process a partition is linear on its
size, this in turn leads to a cost for the whole algorithm
that is the sum of i from 2 to
n-1, that you should be very familiar with.