Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

Question

Given the algorithm

MYSTERY-ALG(n >= 0)
1 if n < 3 then
2     return 1
3 else
4     return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)

I defined a recurrence $ T(n) = \begin{cases} 1 & 0 \leq n < 3 \\ T(\frac{n}{2}) + T(\frac{n}{2} + 1) & \text{otherwise} \end{cases} $ which I guessed to be $O(n)$; I've managed to find suitable $c$ and $n_0$, even an extra variable $b$, from which my bound holds but it fails certain base cases.

Here's my attempt:

Prove $T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1) = O(n)$, where $T([0, 3)) = 1$.

Try 1

Assume $0 \leq ck$ for $k < n$, $c > 0$, must show $T(n) \leq cn$, $\forall n \geq n_0$.

$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$, since $\frac{n}{2} < n$ and $\frac{n}{2} + 1 < n$ for $n > 2 \implies n_0 > 2 \implies T(\frac{n}{2}) \leq \frac{cn}{2}$ and $T(\frac{n}{2} + 1) \leq \frac{cn}{2} + c \implies$

$T(n) \leq \frac{cn}{2} + \frac{cn}{2} + c = cn + c$

$\overset{?}{\leq} cn$ is not possible since $c > 0$.

Try 2

Assume $0 \leq ck - b$ for $k < n$, $c > 0$, $b > 0$ must show $T(n) \leq cn - b$, $\forall n \geq n_0$.

$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$

$\leq \frac{cn}{2} - b + \frac{cn}{2} + c - b = cn - b - b + c = cn - b - (b - c)$

$\leq cn - b$, as long as $b - c \geq 0$

$\implies b \geq c$. From here, it's not clear how to find $b$ and $c$. Strangely, this expression is also independent of $n$.

If we take $c = b = 1$, $n_0 = 3$ then the $T(3) = T(1.5) + T(2.5) = 2 \leq 3 - 1 = 2$ bound holds, but the base case, for example, $T(1) = 1 \leq 1 - 1$ fails.

Is there any way of making this work?

Answer 1

The problem in the question is a good example for two related principles.

• Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to work. However, if the base case is $T(1)$, the inequality does not hold.

  Instead of sticking to proving "$T(n)\le n-1$ for $n\ge0$", you can try proving "$T(n)\le n-1$ for $n\ge 3$" instead. Now the base case is "$T(n)\le n-1$ for $3\le n\lt 6$", which can be proved easily.

  When we want to find some proposition that can be proven by mathematical induction, we can change the domain of the proposition so that the base case in a mathematical induction will be able to succeed. This useful freedom of choice can enable us to make progress. (We could also, of course, change the proposition so that the base case can succeed.)

• If we can prove $T(n)\le n-1$ for $n\ge n_0$ from some $n_0$, it means $T(n)\le n$ for $n\ge n_0$, i.e., $T(n)=O(n)$. It does not matter whether $n_0=1$, or $n_0=3$, or $n_0=2022$.

  The big-$O$ notation is about asymptotic behavior. The behavior when $n$ is small can be ignored.

Two easy exercises
Exercise 1: Show by mathematical induction that $T(n)\le n-1$ for $n\ge3$, considering the base case as when $3\le n\lt 6$.

Exercise 2: Show by mathematical induction that $T(n)\begin{cases}=1,\quad\quad\text{ if }0\le n\lt 3\\\le n-1,\text{ otherwise} \end{cases}$, considering the base case as when $0\le n\lt 3$. This is another way to change the base case.

Answer 2

Your second idea is good, there is no need to start at $n = 1$:

You already proved that for $n\geqslant 3$, $T(n) \leqslant n - 1$.

You can now say that since $n-1 \leqslant n$ and since $T(1)\leqslant 1$ and $T(2)\leqslant 2$, then for all $n$, $T(n) \leqslant n$.

(You can consider $T(n) \leqslant n +1$ if you want to include $n = 0$).