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
  • 2
    $\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$ – Dmitry 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$ – Pranav Rudra Dec 9 '20 at 20:07
  • $\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$ – Dmitry Dec 9 '20 at 20:10
  • $\begingroup$ Understood, thanks for explanation. $\endgroup$ – Pranav Rudra Dec 9 '20 at 20:43
0
$\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$

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.