Quicksort analysis problem This is a problem from a probability textbook, not a CS one, if you are curious. Since I'm too lazy to retype the $\LaTeX$ I will post an ugly stitched screenshot:


This seems ridiculously hard to approach, and it doesn't help that all the difficult problems have no solutions in the textbook (the uselessly easy ones do :P ). How would I attack it?

The question is already broken into pieces in order to help you out.
a) This is the law of total expectation, using the fact that the pivot is chosen randomly.
b) Once we have a pivot, we need to split the remaining $n-1$ numbers into $2$ groups (one comparison each), and then solve the two sub-problems; one of of size $i-1$ and one of size $n-i$, respectively. The recursion comes from plugging in the result from part b to the formula from part a.
c) You can derive this from the recursion in part b.
d) Use the recursion from part c to work out what $C_{n+1}$ should be, using the fact that the harmonic sum $\sum_{i=1}^{n+1} \frac{1}{i}$ is approximately $\log (n+1)$ for large $n$.
