3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ Ah, I see now, I was going about this the wrong way. Thanks $\endgroup$ – tear728 Jul 10 '18 at 17:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.