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

Question

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?

Answer 1

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

Answer 2

If someone is not aware of method to solve this recurrence, then We can solve this by Substitution

Given,

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

Now, going by relation,

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

We will Substitute this in Original Recurrence Relation

Therefore,

$$T(n)=2T(\frac{n}{2})+1$$
$$T(n)=2 \Biggl(2T(\frac{n}{4})+1\Biggr) + 1$$
$$T(n)=2 \Biggl(2T(\frac{n}{2^2})+1\Biggr) + 1$$
$$T(n)=2 \Biggl(2 \Biggl( 2T(\frac{n}{8})+1\Biggr) +1 \Biggr) + 1$$
$$T(n)=2 \Biggl(2 \Biggl( 2T(\frac{n}{2^3})+1\Biggr) +1 \Biggr) + 1$$

Opening Brackets Carefully and Rearranging for Observing Pattern

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

Using Summation formula for Geometric Progression

$$T(n)=2^3T(\frac{n}{2^3})+ 2^0(\frac{2^3-1}{2-1})$$
$$T(n)=2^3T(\frac{n}{2^3})+ {2^3-1}$$

Let us assume that the algorithm takes k iterations.

Therefore, after k iterations.

$$T(n)=2^kT(\frac{n}{2^k})+ {2^k-1}$$

Since, we know T(2). Therefore Put,
$$\frac{n}{2^k}=2$$

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

Therefore, $T(n)$ is asymptotically $O(n)$

Another quick method of solving this is Master Theorem