What is the {best|average}-case cost for Quicksort to sort an array of n elements?
\Theta(n \log n)\Theta(n)\Theta(\log n)\Theta(n^2)While there are a few bad inputs, they are so few as to not affect the average or best cases.
The best thing that can happen is that every pivot split its partition in half. Something close to this happens in the average case.