# Average case running time of quick sort

How to show that the quick-sort algorithm runs in $$O(n^2)$$ time on average ?

Because on average, the expected running time is in $$O(n\log n)$$. The algorithm should not be in exponential time.

• For $O(nlog(n))⊂O(n^m)$ we need $m\gt 1$, otherwise it is not true. BTW, average time and expected time are the same. – zkutch Feb 18 at 5:44
• If you already know that quicksort has expected running time $O(n\log n)$, then in particular, you know that it has expected running time $O(n^{1+\epsilon})$ for all $\epsilon>0$, since $n\log n = O(n^{1+\epsilon})$ for all $\epsilon > 0$. – Yuval Filmus Feb 18 at 8:27

It suffices to show that Quicksort runs in time $$f(n) = O(n^2)$$ in the worst case, since this immediately implies that it also runs in at most $$f(n)$$ time on average.

The recurrence equation that describes the worst-case running time for Quicksort is $$T(n) = T(n-1) + \Theta(n),$$ which has solution $$T(n) = \Theta(n^2)$$.

• Nobody asked for the worst case. – gnasher729 Feb 20 at 17:59
• @gnasher729, Indeed. They asked for a $O(n^2)$ upper bound on the average case, and I'm noting that a $O(n^2)$ upper bound on the worst case already provides the sought upper bound on the average case. Then I'm showing how such worst-case upper bound can be obtained. – Steven Feb 20 at 18:19
• gnasher729 $O$-Notation is an asymptotic upper bound. An asymptotic upper bound for the worst-case-runtime must also be an asymptotic upper bound for the expected runtime. – SometimesBlind Feb 21 at 1:16

It’s a trick question...

O(f(n)) doesn’t only contain functions that grow about as fast as f(n), it also contains all the functions that grow a lot slower than f(n).

So the average time for quicksort is O(n log n), but it is also O(n^2), O(n^5), O(n!) and many other functions.