# Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$

I've already solved the recurrence exactly and found that $$T(n) = n - 1$$. Therefore, I know that $$T(n) = O(n)$$.

However, I'm having trouble showing that $$T(n) = O(n)$$ without solving the recurrence exactly.

My strategy so far has been to prove that $$T(n) \leq cn$$ ($$c$$ is a constant) $$\forall n \geq 2$$ via induction on $$n$$.

Clearly, the base case holds $$T(2) = 1 \leq 2c$$ as long as $$c \geq \frac{1}{2}$$.

For the inductive hypothesis (IH), I assume $$\forall k < n$$, $$T(k) \leq ck$$.

Finally, for the inductive step, I have

\begin{alignat*}{2} T(n) &= 2T\left(\frac{n}{2}\right) + 1 &&\text{ (by definition)}\\ &\leq 2c\left(\frac{n}{2}\right) + 1 &&\text{ (by IH)}\\ &= cn + 1 \end{alignat*}

However, I can't conclude that $$T(n) \leq cn$$ from this. Where am I going wrong?

• It's simpler to prove that $T(k) \le c_1 k - c_2$ (which is $O(k)$) for $k \ge k_0$. – Dmitry Dec 9 '20 at 20:03
• I agree that having a $-c_2$ term would make things easier by allowing for a tighter bound, but is there any way to salvage what I've already done? I feel like there should be a way to prove $T(n) \leq cn$ directly without revising the $cn$ part of it. – Pranav Rudra Dec 9 '20 at 20:07
• I think there is no way. The statement you are trying to prove is simply weaker than what you need. It's common that induction doesn't work for a weaker statement (since your induction hypothesis is too weak). Yours is one example. Another typical example is that, for some problems (e.g. dynamic programming), instead of proving $\forall n\ P(n)$ you should prove $\forall n\ (\forall i \le n\ P(i))$: the induction doesn't work for the first one, while it works for the second one. – Dmitry Dec 9 '20 at 20:10
• Understood, thanks for explanation. – Pranav Rudra Dec 9 '20 at 20:43

If you can solve a recurrence exactly, then there isn't much motivation to solve it approximately, unless the solution is much easier.

Nevertheless, here is a trick that could actually be useful. Define $$S(n) = T(n)+1.$$ Then $$S(n) = T(n) + 1 = 2T(n/2) + 2 = 2S(n/2),$$ and so $$S(2^k) \leq 2^k S(1)$$ by induction.

Let's see what this trick gives you more generally.

Application 1

Consider the recurrence $$A(n) = 2A(\lfloor n/2 \rfloor) + (-1)^n$$, with base case $$A(1)$$.

Define a new recurrence $$T(n) = 2T(\lfloor n/2 \rfloor) + 1$$, with base case $$T(1) = A(1)$$. Prove by induction that $$A(n) \leq T(n)$$. The technique above shows that $$T(n) = O(n)$$, hence $$A(n) = O(n)$$.

Application 2

Consider the recurrence $$B(n) = 2B(\lfloor n/2 \rfloor) + \log n$$, with base case $$B(1)$$.

Define $$R(n) = B(n) + \log n$$. Then $$R(n) = B(n) + \log n = 2B(\lfloor n/2 \rfloor) + 2\log n = 2R(\lfloor n/2 \rfloor) - 2\log \lfloor n/2 \rfloor + 2\log n.$$ You can check that $$2\log n - 2\log \lfloor n/2 \rfloor = O(1)$$, and so the previous technique shows that $$R(n) = O(n)$$. It follows that $$B(n) = O(n)$$.

Application 3

Consider the recurrence $$C(n) = 2C(\lceil n/2 \rceil) + 1$$, with base case $$C(1)$$.

Defining $$D(n) = C(n) + 1$$ with base case $$D(1) = C(1)$$, we see that $$D(n) = 2D(\lceil n/2 \rceil).$$ Let us try to prove by induction that $$D(n) \leq Kn - L$$. Since $$\lceil n/2 \rceil \leq n/2 + 1/2$$, if the induction hypothesis holds for $$\lceil n/2 \rceil$$ then $$D(n) \leq 2K(n/2 + 1/2) - 2L = Kn + K - 2L.$$ Choosing $$L = K$$, we get $$D(n) \leq Kn - L$$. Choosing $$K = D(2)$$, the induction hypothesis holds in the base case $$n=2$$. Altogether, we have proved $$D(n) \leq K(n-1)$$ (for $$n \geq 2$$), and so $$D(n) = O(n)$$, implying $$C(n) = O(n)$$.