Question

50. It can be shown that \({C_B}\)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}\sum\limits_{k = 0}^{n - 1} {{C_k}} \)

for \(n = 1,2, \ldots \), with initial condition \({C_0} = 0\)

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

b) Use Exercise 48 to solve the recurrence relation in part (a) to find an explicit formula for \({C_n}\)

Short answer

(a) Thus, it is verified that $C_n$satisfies the recurrence relation $n{C}_n=(n+1)C_{n-1}+2n$

(b) Thus, the result is$C_n=2(n+1)\sum _{i=1}^n\frac{1}{i+1}$

Step-by-step solution

Linear Homogeneous Recurrence Relations with Constant Coefficients definition

Suppose that\(\left\{ {{a_n}} \right\}\)satisfies the linear non-homogeneous recurrence relation

\({a_n} = {c_1}{a_{n - 1}} + {c_2}{a_{n - 2}} + \cdots + {c_k}{a_{n - k}} + F(n),\)Where\({c_1},{c_2}, \ldots ,{c_k}\)are real numbers, and

\(F(n) = \left( {{b_f}{n^t} + {b_{f - 1}}{n^{t - 1}} + \cdots + {b_1}n + {b_0}} \right){s^n},\)Where\({b_0},{b_1}, \ldots ,{b_t}\)and\(s\)are real numbers.

When\(s\)is not a root of the characteristic equation of the associated linear homogeneous recurrence relation, there is a particular solution of the form\(\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \cdots + {p_{1n}} + {p_0}} \right){s^n}\)

When\(s\)a root of this characteristic equation and its multiplicity is is\(m\), there is a particular solution of the form:\({n^m}\left( {{p_t}{n^t} + {p_{t - 1}}{n^{t - 1}} + \cdots + {p_1}n + {p_0}} \right){s^n}.\)

Use Recurrence Relations

The result from the previous exercise is$f\left(n\right)a_n=g\left(n\right)a_{n-1}+h\left(n\right)n⩾1a_0=C$, then;$a_n=\frac{C+{\sum }_{i=1}^{n}Q\left(i\right)·h\left(i\right)}{g(n+1)Q(n+1)},Q\left(n\right)=\frac{f\left(1\right)·f\left(2\right)·\dots ·f(n-1)}{g\left(1\right)·g\left(2\right)·\dots ·g\left(n\right)}$

$C_n=n+1+\frac{2}{n}\sum _{k=0}^{n-1}{C}_k{C}_0=0$

(a) Let $n⩾1$

\(\begin{array}{l}n{C_n} - (n + 1){C_{n - 1}} = n{C_n} - (n - 1){C_{n - 1}} - 2{C_{n - 1}}\\n{C_n} - (n + 1){C_{n - 1}} = n\left( {n + 1 + \frac{2}{n}\sum\limits_{k = 0}^{n - 1} {{C_k}} } \right) - (n - 1)\left( {(n - 1) + 1 + \frac{2}{{(n - 1)}}\sum\limits_{k = 0}^{(n - 1) - 1} {{C_k}} } \right) - 2{C_{n - 1}}\\n{C_n} - (n + 1){C_{n - 1}} = {n^2} + n + 2\sum\limits_{k = 0}^{n - 1} {{C_k}} - (n - 1)\left( {n + \frac{2}{{n - 1}}\sum\limits_{k = 0}^{n - 2} {{C_k}} } \right) - 2{C_{n - 1}}\\n{C_n} - (n + 1){C_{n - 1}} = {n^2} + n + 2\sum\limits_{k = 0}^{n - 1} {{C_k}} - \left( {{n^2} - n} \right) - 2\sum\limits_{k = 0}^{n - 2} {{C_k}} - 2{C_{n - 1}}\\n{C_n} - (n + 1){C_{n - 1}} = 2n + 2\sum\limits_{k = 0}^{n - 1} {{C_k}} - 2\sum\limits_{k = 0}^{n - 1} {{C_k}} \\n{C_n} - (n + 1){C_{n - 1}} = 2n + 0\\n{C_n} - (n + 1){C_{n - 1}} = 2n\end{array}\)

We then obtained\(n{C_n} - (n + 1){C_{n - 1}} = 2n\), which equivalent is with:

\(n{C_n} = (n + 1){C_{n - 1}} + 2n\).

Use Recurrence Relations for part (b)

(b).

Equation is:\(n{C_n} = (n + 1){C_{n - 1}} + 2n{C_0} = 0\)

Since\(f(n){a_n} = g(n){a_{n - 1}} + h(n)\)and\({a_0} = C\)(in general):

\(f(n) = ng(n) = n + 1h(n) = 2nC = 0\)

Let us first determine\(Q(n) = \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}}\)

\(\begin{array}{c}Q(n) = \frac{{f(1) \cdot f(2) \cdot \ldots \cdot f(n - 1)}}{{g(1) \cdot g(2) \cdot \ldots \cdot g(n)}}\\ = \frac{{1 \cdot 2 \cdot \ldots \cdot (n - 1)}}{{2 \cdot 3 \cdot \ldots \cdot (n + 1)}}\\ = \frac{1}{{n \cdot (n + 1)}}\end{array}\)

Then we obtain:

\(\sum\limits_{i = 1}^n Q (i)h(i) = \sum\limits_{i = 1}^n {\frac{{2i}}{{i \cdot (i + 1)}}} = \sum\limits_{i = 1}^n {\frac{2}{{i + 1}}} \)

\(\sum\limits_{i = 1}^n Q (i)h(i) = \sum\limits_{i = 1}^n {\frac{{2i}}{{i \cdot (i + 1)}}} = \sum\limits_{i = 1}^n {\frac{2}{{i + 1}}} \)

Using the result of the previous exercise, we then obtain:

\(\begin{array}{c}{C_n} = \frac{{C + \sum\limits_{i = 1}^n Q (i) \cdot h(i)}}{{g(n + 1)Q(n + 1)}}\\{C_n} = \frac{{0 + \sum\limits_{i = 1}^n {\frac{2}{{i + 1}}} }}{{(n + 2) \cdot \frac{1}{{(n + 1)(n + 2)}}}}\\{C_n} = \frac{{\sum\limits_{i = 1}^n {\frac{2}{{i + 1}}} }}{{\frac{1}{{n + 1}}}}\\{C_n} = (n + 1)\sum\limits_{i = 1}^n {\frac{2}{{i + 1}}} \\{C_n} = 2(n + 1)\sum\limits_{i = 1}^n {\frac{1}{{i + 1}}} \end{array}\)

Thus, the result is\({C_n} = 2(n + 1)\sum\limits_{i = 1}^n {\frac{1}{{i + 1}}} \)