how to bound the probability that quicksort takes greater than n lg n time?
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 &gt; 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:


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.
The argument of Theorem 12.4 can be strengthened to show that for each $k&gt;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$.
Putting the two ingredients together yields the problem.