0
$\begingroup$

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.

$\endgroup$
2
  • $\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 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$ – Yuval Filmus Feb 18 at 8:27
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Nobody asked for the worst case. $\endgroup$ – gnasher729 Feb 20 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 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$ – SometimesBlind Feb 21 at 1:16
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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