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.

  • $\begingroup$ 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. $\endgroup$
    – zkutch
    Feb 18, 2021 at 5:44
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 18, 2021 at 8:27

2 Answers 2


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

  • $\begingroup$ Nobody asked for the worst case. $\endgroup$
    – gnasher729
    Feb 20, 2021 at 17:59
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Feb 20, 2021 at 18:19
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 21, 2021 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.