1
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ It's simpler to prove that $T(k) \le c_1 k - c_2$ (which is $O(k)$) for $k \ge k_0$. $\endgroup$
    – user114966
    Dec 9 '20 at 20:03
  • $\begingroup$ 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. $\endgroup$ Dec 9 '20 at 20:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – user114966
    Dec 9 '20 at 20:10
  • $\begingroup$ Understood, thanks for explanation. $\endgroup$ Dec 9 '20 at 20:43
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is this material taken from somewhere? $\endgroup$ Sep 18 at 8:13
  • $\begingroup$ No. It was solved on paper by me and typed using Mathematical Tools provided by this Site. $\endgroup$ Sep 18 at 10:00

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.