search
Log In
2 votes
22 views

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}.$
in Combinatory 22 views

Please log in or register to answer this question.

Related questions

1 vote
0 answers
1
39 views
Prove Theorem $6:$Suppose that $\{a_{n}\}$ satisfies the liner nonhomogeneous recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} + F(n),$ where $c_{1}.c_{2},\dots,c_{k}$ ... is $m,$ there is a particular solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$
asked May 6 in Combinatory Lakshman Patel RJIT 39 views
0 votes
0 answers
2
25 views
Prove Theorem $4:$ Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation $r^{k}-c_{1}r^{k-1}-\dots c_{k} = 0$ has $t$ distinct roots $r_{1},r_{2},\dots,r_{t}$ with multiplicities $m_{1},m_{2},\dots,m_{t},$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$
asked May 6 in Combinatory Lakshman Patel RJIT 25 views
0 votes
0 answers
3
29 views
Solve the recurrence relation $T (n) = nT^{2}(n/2)$ with initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer $k.$ [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = \log T (2^{k})$ to obtain a linear nonhomogeneous recurrence relation.]
asked May 6 in Combinatory Lakshman Patel RJIT 29 views
...