1
$\begingroup$

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$$?

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

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.

If OP's intention is emphasizing how he (meaning them, Donald Knuth and Oren Patashnik) get the recurrence relation, then I can only honestly say I have no credible idea beyond a few educated guesses.

If OP's intention is just to know how to deduce the recurrence relation, then the wikipedia item on quicksort is a nice answer, which I have copied below with minor modification to fit current question.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.