# Exercise 12.4.5

$\star$ Consider

`RANDOMIZED-QUICKSORT`

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

**UNSOLVED**. Yeah, this formulation is very confusing and I don't get it.

Let's move on.