Chapter 8.2, Problem 50E

It can be shown that $C_n$, the average number of comparisons made by the quick sort algorithm (described in preamble to Exercise 50 in Section 5.4), when sorting n elements in random order, satisfies the recurrence relation

$C_n=n+1+\frac{2}{n}{\displaystyle \underset{k=0}{\overset{n-1}{\sum }}{C}_k}$

for n = 1, 2, ..., with initial condition $C_0=0$ .

a) Show that $\left\{C_n\right\}$also satisfies the recurrence relation $n{C}_n=\left(n+1\right)C_{n-1}+2n$for n = 1, 2,

b) Use Exercise 48 to solve the recurrence relation in part (a) to find an explicit formula for C.