I'm trying to work my way through Concrete Mathematics (2nd Edition).
I'm struggling to understand the transition for the analysis of the quick sort algorithm from the recurrence to the harmonic number representation.
According to the text, the average number of comparison steps made by quicksort can be represented by the following recurrence:
$$C_0 = 0 ;$$
$$nC_n = (n + 1) C_{n-1} + 2n ;\, for\,\, n > 0 $$
Using [2.9] $a_nT_n = b_nT_{n-1} + c_n$, then for this recurrence $a_n=n, b_n=(n+1), c_n=2n$.
The solution to this recurrence can be represented by
$$\
T_n = \frac{1}{s_na_n}\left({s_1b_1T_0} + \sum_{k=1}^ns_kc_k\right) …[2.10]
$$
Where
$$ s_n = \frac{a_{n-1}a_{n-2}…a_1}{b_nb_{n-1}..b_2} = \frac{2}{(n+1)n}$$
Based on these formulae, the author concludes that
$$C_n = 2(n+1)\sum_{k=1}^n\frac{1}{k+1}$$
I am struggling to understand how $s_kc_k$ can equal $\frac{1}{k+1}$ and not $\frac{4}{k+1}$ because if $s_n=\frac{2}{(n+1)n}$ and $c_n=2n$, then i would expect $s_kc_k$ to equal $\frac{2}{(k+1)k} \times 2k = \frac{4k}{(k+1)k} = \frac{4}{k+1}$
Best Answer
Yes, But calculate also $\frac{1}{s_n a_n}$ and you will get the expected result when multiplying by your result.