Solving recurrences by substitution

Question

I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method. Given the recurrence:

$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1, $$

We guess that the solution is $T(n) = O(n)$. Thus we try to show that $T(n) \le cn$. By substituting our guess, we are left with,

$T(n) = cn + 1$, which is not $\le cn$.

Makes sense. But then in the next paragraph, he writes that if we guess for $T(n) = O(n^2)$, we can make the solution work. However, wouldn't the solution still be off by a constant of 1, since:

$$T(n) = O(n^2) = 2c(n/2)^2 + 1?$$

Or am I not substituting correctly for $O(n^2)$? Seems like I'm missing something trivial about this.

Answer 1

Assuming for simplicity that $n$ is even, if we guess that $T(n) \leq C^2n$ then we can prove our guess by induction (for powers of 2) for an appropriate value of $C$ since $$ T(n) = 2T(n/2) + 1 \leq C(n/2)^2 + 1 = \frac{C}{4} n^2 + 1 $$ is smaller than $Cn^2$ as long as $C \geq 4/3$ (assuming $n \ge 1$).

Answer 2

It's worth noting that the substitution method is a alternative name for proof by induction. So, in the end, (1) you need to get exactly the same hypotheses. Also, it needs to (2) work for all $n$.

For example, using the hypoteses $T(n) \leq cn^2$,

\begin{eqnarray*} T(n) &=& T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1 \\ &\leq& c (\lfloor n/2 \rfloor)^2 + c(\lceil n/2 \rceil)^2 + 1 \\ &=& c \frac{(n-1)^2}{4} + c\frac{(n+1)^2}{4} + 1 \quad\quad\quad (\textrm{assuming $n$ odd})\\ &=& c \frac{n^2-2n+1}{4} + c\frac{n^2 +2n +1}{4} + 1 \\ &=& \frac{cn^2+c+2}{2} \\ &\leq& cn^2 \quad\quad\quad(\textrm{if } c \ge 2/(n^2-1))\\ \end{eqnarray*}

Note that, in the last line, (1) you got exactly the same hypotheses. You also need that (2) it works for all $n$, but this proof only works for $n$ odd. So, in a similar way, you can do the rest of the proof for the even case. Only after that you have finished the induction proof.