0
$\begingroup$

My question is strongly related to the one asked here:

How do I show T(n) = 2T(n-1) + k is O(2^n)?

$$T(n)=2T(n-1)+1$$

Going with the steps, I reached the point where:

$$c*2^{n}\geq c*2^{n}+1$$ which implies $$0\geq 1$$ which is false for all possible values of $c$ and thus the claim $T(n)=O(2^{n})$ should be incorrect.

However, most answers to the question just mention that in such case, one should try alternative methods to find/prove the upper bound. I don't understand how should I be able to justify that, is this a scenario in which "induction fails" ? because I've never heard of such one. enter image description here

Improve this question
$\endgroup$
4
  • $\begingroup$ There are many ways to solve this recurrence. For example, if you define $f(n)=T(n)+1$ we get that your recurrence becomes $f(n)=2f(n-1)$. If $f(0)=c$, then it follows that $f(n)=c2^n$. In fact $f(0)=c2^n=c$ and if $f(n-1)=c2^{n-1}$, then $f(n)=2f(n-1)=2c2^{n-1}=c2^n$. Induction implies that for all $n$ we have $f(n)=c2^n$. Then $T(n)=c2^n-1$. $\endgroup$
    – plop
    Commented Nov 20, 2020 at 14:12
  • $\begingroup$ I understand that I can do this in better ways, I'm just concerned because performing induction in the way I did concludes that the claim is wrong, i.e. that $O(2^{n})$ cannot be taken as an upper bound even though it is. $\endgroup$
    – Essam
    Commented Nov 20, 2020 at 17:15
  • $\begingroup$ Then write what you did. Otherwise there is no way to know what you did wrong. $\endgroup$
    – plop
    Commented Nov 20, 2020 at 21:24
  • $\begingroup$ I attached a picture of that, check the second guess. (Note that I was just checking what induction would say about that, I already did, using two other different methods prove that its $\Theta(2^{n})$. $\endgroup$
    – Essam
    Commented Nov 20, 2020 at 21:42

2 Answers 2

Reset to default
1
$\begingroup$

More interesting than solving the recurrence is to show where exactly your complete induction proof went wrong.

To show a statement S(n) by complete induction you prove manually that S(n) is true for all $n ≤ n_0$ for some $n_0$, and then you show that for $n > n_0$, if S(n') is true for all n' < n, then S(n) is also true. That's a quite general form of complete induction; the simplest form is to show that S(0) is true, and if S(n-1) is true then S(n) is also true.

You picked the statement S(n): T(n) ≤ $c \cdot 2^n$. That's true for n = 0 as long as T(0) ≤ c. Unfortunately, S(n-1) doesn't imply S(n): S(n-1) means $T(n-1) ≤ c \cdot 2^n$, so $T(n) = 2T(n-1) + 1 ≤ 2c \cdot 2^{n-1} + 1 = c \cdot 2^n + 1$. And that doesn't prove S(n).

This doesn't mean the statement S(n) is wrong; it just means you failed to prove it. But with complete induction, if you make the induction statement stronger, then you also make the pieces that you can use in your induction proof stronger.

So now we claim S(n): $T(n) ≤ c \cdot 2^n - 1$. That's a stronger statement. It is true for n = 0 if $T(0) ≤ c - 1$ or c ≥ T(0) + 1. And now S(n-1) means $T(n-1) ≤ c \cdot 2^n - 1$, and therefore $T(n) = 2T(n-1) + 1 ≤ 2(c \cdot 2^{n-1} - 1) + 1 = c \cdot 2^n - 1$, which is exactly the statement S(n).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is all I needed to know :))), big thanks. $\endgroup$
    – Essam
    Commented Nov 21, 2020 at 6:40
1
$\begingroup$

Ok lets try solving this by substitution ,

$T(n) = 2T(n-1) + 1$

from this we know , $T(n-1) = 2T(n-2) + 1$

so $T(n) = 2(2T(n-2) + 1) + 1$

$T(n) = 2^2T(n-2) + 3$

lets substitute one more time

$T(n-2) = 2^2T(n-3) + 1$

$T(n) = 2^2(2T(n-3)+1) + 3$

$T(n) = 2^3 T(n-3) + 7$

Hopefully you can notice the pattern now $T(n) = 2^{k}T(n-k) + 2^{k}-1$

So , for $k = n$

$T(n) = 2^{n}T(n-n) + 2^{n}-1$ , we know that $T(n-n) = T(0) = 1$

$T(n) = 2^{n} + 2^{n}-1$

so clearly , $T(n) = O(2^n)$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.