# substitution method on T(n) = T(floor(n/2)) + n recurrence

While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem.

Why we assumed that this inequality holds for all positive $$m, in particular for $$m=\lfloor n/2\rfloor$$? on what basis do we choose this $$m$$ and why do we need it. Appreciate your answers.

EDIT: Excerpt is from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

• Are you familiar with complete induction? Jan 30, 2021 at 13:47
• We choose this value of $m$ since this is the value relevant for proving the inductive step. Jan 30, 2021 at 13:48

Here, the base case is when $$n = 1$$. You might want to verify that $$T[1] = O(1)$$. And, if that is the case, then $$T[1]$$ satisfies the induction hypothesis, i.e., $$T[n] \leq c \cdot n \log n$$ for $$n = 1$$ and sufficiently large $$c$$. Now, you would like to prove that the hypothesis also holds for other values of $$n$$.
For this, you assume that $$T[m] \leq c \cdot m \log m$$ for any $$m. And, suppose using this you could prove that $$T[n] \leq c \cdot n \log n$$. Then, it will imply that the hypothesis is indeed the correct hypothesis for every $$n$$. This is because you can apply this proof step to the base case. And, it will give you the correctness of the hypothesis on $$T[2]$$. Then, you apply the proof step on $$T[2]$$ and it will give you the correctness on $$T[3]$$, and so on... Therefore, it proves that the hypothesis is indeed the correct hypothesis for all value of $$n$$, for sufficiently large $$c$$.