1
$\begingroup$

In the fourth edition of Sedgewick's Algorithms, it's claimed that the running time of QuickSort is $\sim 1.39n\log_2 n$. I'm trying to find a "simple" proof and explanation of this.

All I know is that the total running time obeys $$C_n = C_{\mathrm{partitioning}} + C_{\mathrm{leftArray}} + C_{\mathrm{rightarray}}$$

and that quicksort's average case is about $2n\log_\mathrm{e}n$.

$\endgroup$
  • $\begingroup$ Where did you see that claim? Something so specific that it states a constant to three significant figures is going to depend on a specific implementation and is unlikely to have a particularly simple explanation. $\endgroup$ – David Richerby Jun 15 '17 at 9:28
  • $\begingroup$ In the book "Algorithms fourth edition" by Robert Sedgewick. >"In summary, you can be sure that the running time of algorithm 2.5 (quicksort) will be within a constant factor of 1.39n lg n whenever it it used to sort n items" also it's with tilde notation so it's probably not accurate but an approximation. $\endgroup$ – Edward Jun 15 '17 at 9:31
  • 3
    $\begingroup$ If the claim is that it is "within a constant factor of $1.39 n \log n$", then it seems odd to bother with the factor 1.39 in the first place. $\endgroup$ – Pontus Jun 15 '17 at 9:45
  • 1
    $\begingroup$ @Pontus There is a little more context in the book. $\endgroup$ – Raphael Jun 15 '17 at 10:41
  • 1
    $\begingroup$ Not everything has a simple proof. Sometimes you need to do some calculation. I imagine that $1.39n\log_2n$ is the average number of comparisons over a random permutation, and that the number of comparisons is concentrated, meaning that it is within $\pm O(n)$ (or better) with high probability. $\endgroup$ – Yuval Filmus Jun 15 '17 at 10:42
4
$\begingroup$

it's claimed that the running time of QuickSort is $∼1.39\,n\log_2n$

I don't have the book handy, but it it most certainly does not claim this. That figure is the result of a close analysis of a very specific cost measure (which "time" is not); expected number of comparisons, if I remember correctly.

The proof is given in the book, if I recall correctly.

quicksort's average case is about $2n\log_e n$.

This is basically the same figure since $1.39 \approx \frac{2}{\log_2 e}$, the difference probably being a rounding artifact.

From your comment, quoting Sedgewick/Wayne:

In summary, you can be sure that the running time of algorithm 2.5 (quicksort) will be within a constant factor of $1.39n \lg n$ whenever it it used to sort n items.

This only states that the (expected) running time is in $\Theta(n \lg n)$; this follows from the (expected) number of comparisons being what it is, plus that comparison is a dominant operation in Quicksort.

For what it's worth, the formulation "you can be sure" without context is misleading since it seems to ignore the worst-case, and the asymptotic nature of the result.

$\endgroup$
  • $\begingroup$ I've found my college slides in the meantime, explaining the formula. Still it's not so clear for me. When I have time I'll try to update the question/answer. You can find an excerpt in the following link imgur.com/a/Bc9X3 comments are in dutch, credits go to my professor dr. ir. Philip Dutré. (professor Dutré if you're reading this, I'll promise to pay more attention during class in the future) $\endgroup$ – Edward Jun 15 '17 at 11:27
  • 1
    $\begingroup$ @Edward Yes. The short of it is to a) set up the recurrence and b) solve it. Solving it towards a $\sim$-asymptotic is more intricate than towards a $\Theta$-asymptotic, that's for sure. Kudos to your professor for teaching you how! That said, as this proof is covered amptly in the literature, I see little use of reproducing it here. I suggest you have at it again; you are very welcome to ask any specific questions about details of the proof you may encounter! Best make new posts for them. Best of luck! $\endgroup$ – Raphael Jun 15 '17 at 12:45

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.