Finding a lower bound for an algorithm using the guess/verify method

Question

Hi everyone, I am trying to work out a few guesses on algorithm complexity, but every time I attempt to guess using an exponential time, my guess/verify method seems to fail. I am sure I am doing something absurdly wrong, I just can't find it myself.

For Example, if I have the recurrence T(n) = 2T(n-1) + T(n-2) + 1 , where T(1) = 0 and T(2) = 1.

By iterating it a few times and plugging the vales n=3,4,5,6,7,8... we can observe that for any value of n>=8, T(n) > 2^n, therefore 2^n is not an upper bound.

So, knowing that information I try to guess that T(n)=O(2^n)

T(n) <= C(2^n)

2T(n-1)+T(n-2)+1 <= C(2^n)

2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n)

C(2^n)-C(2^n+2^(n-2)) >= 1

C(-2^(n-2)) >= 1

C >= 1/(2^(n-2)) | as n-> infinity, the expression goes to zero

Wouldn't this mean that my guess is too high? However, I know that that is not the case. Can anyone see where exactly am I butchering the theory? Thanks.

Answer 1

The transition from 2T(n-1)+T(n-2)+1 <= C(2^n) to 2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n) is wrong.
if T(n) <= C(2^n) you can infer that 2T(n-1)+T(n-2)+1 <= 2C(2^(n-1))+C(2^(n-2))+1 but not that 2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n).

Note that 2C(2^(n-1))=C(2^n) so it must be that 2C(2^(n-1))+C(2^(n-2))+1 >= c(2^n).