# quicksort recurrence relation

In Concrete Mathematics Textbook by Donald Knuth and Oren Patashnik , ch.2 Sum ,sec2.2
He wrote:

The average number of comparison steps made by quicksort when it's applied to $n$ items in random order satisfies the recurrence : $$C_0=0;$$ $$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$$

The question is how he get the relation :

$$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$$?

• Well, what does the book say? What do you end up with when you take a close look at the algorithm? – Raphael Aug 22 '18 at 9:55
• I think $n+1$ should be $n-1$. – Yuval Filmus Aug 23 '18 at 4:01

Unfortunately, that textbook says nothing about how to deduce that particular recurrence relation, although it has plenty of examples on how to obtain a recurrence relation. In fact, I cannot understand $C_1=1+1+C_0 =2$, which says that we need two comparisons to sort 1 item using quicksort.
Assume that there are no duplicates. When the input is a random permutation, the rank of the pivot is uniform random from 0 to $n − 1$. Then the resulting parts of the partition have sizes i and $n − i − 1$, and $i$ is uniform random from 0 to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the following recurrence relation.
$$C(n)=n-1+{\frac 1n}\sum_{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac 2n}\sum _{i=0}^{n-1}C(i)$$
Please note that in the wikipedia item, $C(1)=1-1+0=0$, which say that we need no comparison to sort 1 item, which looks much more reasonable to me