# Solving recurrences by substitution method: why can I introduce new constants?

I am solving an exercise from the book of Cormen et al. (Introduction To Algorithms). The task is:

Show that solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O(\lg n)$

So, by big-O definition I need to prove that, for some $c$,

$$T(n) \le c\lg n\,.$$

My take on it was: \begin{align*} T(n) &\leq c\lg(\lceil n/2\rceil) + 1 \\ &< c\lg(n/2 + 1) + 1 \\ &= c\lg(n+2) - c + 1\,. \end{align*} As this doesn't seem satisfactory I looked up a solution and the author after getting to the same stage as me decided to introduce a new arbitrary constant $d$: \begin{align*} T(n) &\le c\lg(\lceil n/2-d\rceil) + 1 \\ &< c\lg(n/2+1-d) + 1 \\ &< c\lg((n-2d+2)/2) + 1 \\ &= c\lg(n-2d+2) - c + 1 \\ &= c\lg(n-d-(d-2)) - c + 1\,. \end{align*}

And now, for $d \ge 2$, $c \ge 1$ and $n > d$,

$$c\lg(n-d-(d-2)) - c + 1 \le c\lg(n-d)\,.$$

What I don't understand is how does it prove that $T(n) \le c\lg n$? Cormen et al. make a big point that you have to prove the exact form of the inductive hypothesis which in this case was $T(n) \le c\lg n$. They then go on to show example similar to one above.

How is that the exact form of the inductive hypothesis? This doesn't seem to fit the big-O definition. When can I omit constants or cheat them away? When is it wrong?

• Please, check if this can help. – kentilla Nov 12 '15 at 20:42

I am guessing that the book wants you to proof the stronger hypothesis $T(n) \leq c\log( n -d)$ which implies $T(n) \leq c log(n)$ is also true ( because $n \geq n -d$ for $d\geq 0$. )