0

I have the following reccurence relation:

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

I tried to expand it but it didn't get me anywhere and I'm stuck. Can someone help please?

CnR
  • 351
  • 1
  • 6
  • 15
  • 3
    possible duplicate of [Computational complexity of Fibonacci Sequence](http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) – Ondrej Svejdar Sep 11 '14 at 16:00

1 Answers1

0

expand it like t(n-1)=t(n-2)+t(n-3) and t(n-2)=t(n-3)+t(n-4)
it will give 2+4+8+........2^n=O(2^n) solving gp

mukesh
  • 111
  • 2
  • 1