Is $T(n)≤ cn \lg n$ the inductive hypothesis for the solution in Introduction to Algorithms, 3rd Edition Section 4.3?

23 Views Asked by At

Section 4.3 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" uses the following recurrence as an example to illustrate the substitution method.

$T(n) = 2T(\lfloor{n/2}\rfloor)+n \tag{4.19}$

the guess is T(n) = O(n \lg n), The substitution method requires us to prove that

$$T(n)≤ cn \lg n \tag{1}$$

or

$$T(m)≤ cm lg m \tag{2}$$

let $m=\lfloor{n/2}\rfloor$, then equation (2) would be

$$T(\lfloor{n/2}\rfloor) \leq c\lfloor{n/2}\rfloor \lg (\lfloor{n/2}\rfloor) \tag{3}$$

which is exactly what that section gives.

In this context, is equation (2) the inductive hypothesis for the solution?