Search code examples
algorithmclrs

Recurrence in analysis of SELECT algorithm

In CLRS (2/e, page 191, section 9.3) the analysis of the SELECT algorithm for finding the ith smallest element in an array is presented with the following induction proof:

1.  T(n) <= c celing(n/5) + c(7n/10 + 6) + an
2.       <= cn/5 + c + 7cn/10 + 6c + an
3.       = 9cn/10 + 7c + an
4.       = cn + (-cn/10 + 7c + an)
5.       = cn,  when -cn/10 + 7c + an <= 0

I understand the algorithm, but two manipulations in the proof have me stumped a bit.

Question 1: in line 2, where did the extra c term comee from (second term)? c multiplied through the (7n/10 + 6) term gives 7cn/10 + 6c.

Question 2: in line 4, how did we get from 9cn/10 to cn + (-cn/10 ...)? Where did the 9 coefficient go?

This is not homework

Thank you!

Solution
    1. The extra c is from c*celing(n/5) - consider n/5 = 10.2 - then c * ceiling(n/5) = 11c > cn/5 so we need to add an extra c.
    2. 9cn/10 = (10-1)cn/10 = 10cn/10 - cn/10 = cn - cn/10 ... = cn + (-cn/10 ...)