# Proof that quicksort's running time is ∼1.39 n log n

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

• 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. Jun 15, 2017 at 9:28
• 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. Jun 15, 2017 at 9:31
• 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. Jun 15, 2017 at 9:45
• @Pontus There is a little more context in the book. Jun 15, 2017 at 10:41
• 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. Jun 15, 2017 at 10:42

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.

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.
• @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! Jun 15, 2017 at 12:45