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


Yes, But calculate also $\frac{1}{s_n a_n}$ and you will get the expected result when multiplying by your result.

  • 1
    $\begingroup$ Ah I'm a twit, need to use the third identity here and pull the 4 to the left of the summation and multiply by 1/snan. Thanks @marco $\endgroup$ – noconnor Nov 8 '18 at 10:28

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.