edited by
250 views
2 votes
2 votes

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

$$C_{n} = 1 + n + \dfrac{2}{n}\sum_{k=0}^{n-1}C_{k}$$
for $n = 1, 2, \dots,$ with initial condition $C_{0} = 0.$

  1. Show that $\{C_{n}\}$ also satisfies the recurrence relation $nC_{n} = (n + 1)C_{n-1} + 2n \:\text{for}\: n = 1, 2, \dots$
  2. Use question $48$ to solve the recurrence relation in part $(A)$ to find an explicit formula for $C_{n}.$
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
4
admin asked May 6, 2020
220 views
Use question $48$ to solve the recurrence relation $(n + 1)a_{n} = (n + 3)a_{n-1} + n, \:\text{for}\: n \geq 1, \:\text{with}\: a_{0} = 1$