how to bound the probability that quicksort takes greater than n lg n time?

Question

I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed)

Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > 0, all but O(1/nᵏ) of the n! input permutations yield an O(n lg n) running time.

By RANDOMIZED-QUICKSORT, they simply mean quicksort with the pivot randomly selected from interval being partitioned, as opposed to always being chosen as, say the last element or something.

A previous thread on this same question had a single answer, which consisted entirely of a dead link plus a working link that leads to a set of (in my opinion) poorly-written notes for an undergraduate class, that does not answer the question, only having a very brief discussion of a particular case of quicksort with n ≈ 20.

I'm not even sure how to rigorously pose the question; my best shot is this:

Prove that for any k > 0, there exists positive constants a, b, and n₀ such that for all n > n₀, the probability that RANDOMIZED-QUICKSORT makes more than a n lg n comparisons is less than b /nᵏ:

A similar problem appears in Knuth's The Art of Computer Programming vol 3, Sorting and Searching, as problem 42 on page 137 (with some minor notational edits for clarity):

For any real number c > 0, prove that the probability is less than exp(-c) that quicksort will make more than (c + 1)(n + 1)H comparisons when sorting random data, where H = 1 + 1/2 + 1/3 ... 1/n. (This upper bound is especially interesting when c is, say, nʰ, where h is small and positive).

The solution to this problem is given at the end of the book, and consists only of the following:

This is a special case of a general theorem due to R. M. Karp, see JACM 41 (1994), 1136-1150, section 2.8. Significantly sharper asymptotic bounds for tails of the quicksort distributions have been obtained by McDiarmid and Hayward, J. Algorithms 21 (1996), 476-507.

I hunted down the Karp paper, and it indeed proves the result from the Knuth problem.

While CLRS seemingly refers to Knuth for a great deal of the former's material, it seems to be that the result that CLRS is asking us to prove is actually stronger than the result in the Knuth problem. In particular if we take the parameter c in Knuth's result to be any c(n) = ω(1), e.g. even something extremely slowly growing like c(n) = ln ln ln n, then the Karp result says that the probability is less than exp[-c(n)] that quicksort will make more than [c(n) + 1](n + 1)H comparisons. Since H = Θ(lg n), this number is Θ[c(n) n lg n], and since we have defined c(n) = ω(1), this number is ω[ n lg n ], with maximum generality. However, with the choice c(n) = ln ln ln n, the upper bound of the probability is exp[-c(n)] = 1 / ln ln n, which is a much weaker upper bound than what CLRS is asking for: less than O(1/nᵏ) for any constant k > 0.

My questions are the following: is my interpretation of the CLRS question (the quoted block above, immediately after I say "my best shot is this") correct? If not, what, specifically, is CLRS actually asking us to prove? Also, what is the relationship between the CLRS question and the Knuth question? Is the Knuth result weaker than the CLRS result? If so, does the CLRS result draw on more recent published research than the 1994 Karp paper cited in Knuth's "answer"?

Also, some further relevant reading: the McDiarmid paper that Knuth's answer points to cites a 1991 paper by Rosler, who showed that

$$ \Pr\left[\left|\frac{Q_{n}}{E[Q_{n}]}-1\right|>\varepsilon\right]=O\left(\frac{1}{n^{k}}\right) $$

where $Q_n$ is a random variable indicating the number of comparisons made by quicksort on an input of size $n$, $\varepsilon$ is a fixed constant, and $k$ is any positive real number. It seems likely that this is the source of the result asked for in the original CLRS problem, although the formulation of the probability in the above equation does not seem extremely obviously equivalent to the CLRS phrasing.

Answer 1

The exercise is extremely poorly worded. The problem is that Randomized-Quicksort is a randomized algorithm, and so it doesn't have a "running time", or rather, its running time is a random variable. I suspect that this is a typo, and that the intension was to analyze the deterministic Quicksort algorithm. Assuming this correction, here is a more formal version of the exercise:

Show that for all $k > 0$ there exist constants $a_k,b_k$ such that for all $n$, there exists a subset $S \subseteq S_n$ (where $S_n$ is the set of all permutations of $1,\ldots,n$) of size at most $(a_k/n^k) n!$ such that for all $\pi \in S_n \setminus S$, the running time of Quicksort on $\pi$ is at most $b_k n \log n$.

In order to prove the exercise, presumably you need to use material from Theorem 12.4, which states that the expected height of a randomly built binary search tree of size $n$ (formed by choosing a random permutation in $S_n$ and adding the elements to a binary search tree in that order) is $O(\log n)$. You then argue roughly as follows:

1. When running Quicksort on a permutation in $S_n$, the running time is $O(nh)$, where $h$ is the height of the binary search tree formed from the permutation.

2. The argument of Theorem 12.4 can be strengthened to show that for each $k>0$ there exist $a_k,b_k$ such that when constructing a random binary search tree, the probability that the height exceeds $b_k \log n$ is at most $a_k/n^k$.

3. Putting the two ingredients together yields the problem.

Answer 2

Here's a possible answer to the original CLRS question itself, based on the outline provided in the accepted answer above.

Let $X_n$ be the random variable indicating the height of a randomly-built binary search tree on $n$ distinct keys. Page 302 of CLRS showed that

$$ \mathrm{E}\left[2^{X_n}\right]\leq \frac{1}{4} \left(\begin{array}{c} n+3\\ 3 \end{array}\right) = O(n^3) $$

By Markov's inequality (proven in exercise C.3-6 of CLRS), we have for any $t > 0$:

$$ \Pr\left\{ X_{n}\geq \lg t\right\} = \Pr\left\{ 2^{X_{n}}\geq t \right\} \leq\frac{\mathrm{E}[2^{X_{n}}]}{t}=O\left( n^3t^{-1} \right) $$

Hence, choosing $t = n^{3+k}$ for any $k>0$, we have

$$ \Pr\left\{ X_{n}\geq (k+3)\lg n\right\} = O\left( n^{-k} \right) $$

Mapping this back to the quicksort problem, as discussed in the accepted answer above, we obtain that the probability of quicksort taking time larger than $(k+3) n \lg n$ is $O\left( n^{-k} \right)$, which completes the proof.

Note that this result is useful because the set of sequences that take time larger than $(k+3) n \lg n$ includes, as a subset, all the sequences that take worse-than-average behavior, such as for example already-sorted sequences, which elicit $\Theta(n^2)$ runtime, as well as everything in between the average and worst, e.g. $\omega(n \lg n)$ and $o(n^2)$. Hence, bounding the probability of this set also bounds the probability of the subset.