The solution for solving the following recurrence with the substitution method involves adding the a constant inside the recurrence, which is confusing to me. This is question 4.3-2 in the CLRS textbook.
Show that $T(n)=T(n/2) + 1$ is $O(lgn)$
The solution states that the guess should be $T(n) leq clg(n-2)$. I understand the need to add the n-2 for the proof. What I don’t understand is the first step in the algebra.
$(Tn) leq clg(n/2 + 1 – 2) + 1$ ( Don’t understand why 1 is added inside the parenthesis.)
$ leq clg((n-2)/2) + 1$
$ = clg(n-2) – clg2 + 1 $
$ leq clg(n – 2) $
What I don’t understand is step 1 of the breakdown. Why is there a 1 added to n/2? It might be something minor in the math that I’m missing but I can’t seem to understand it. My only guess is that it is added in the recurrence to match the + 1 at the end of the equation.