Time complexity of fibonacci series

Question

How to find time complexity of fibonacci series ? Answer is given O (2^n). But i couldn't get it

Recurrence eq :

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

By back substitution i got,

T(n) = T(n-1) + T(n-2) + c
T(n) = 2*T(n-2) + T(n-3) + 2c
T(n) = 3*T(n-3) + 2*T(n-4) + 4c
T(n) = 5*T(n-4) + 3*T(n-5) + 7c
etc ...

 I'm unable to proceed to next steps..

After that what would be the procedure? 

Could anyone please explain?

Comments

I suggest better to use tree method

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

you will get series like this

=c+2c+2^2c+2^3c+..........2^kc

=c(2^(k+1)-1)/(2-1)

here if you use tree you will get k=n

so you will get time complexity O(2^n).

Answer 1

$T(n) \leq 2T(n-1)$

Solving we get.

$\Rightarrow T(n) = O(2^{n})$

Comments

T(n) = T(n - 1) + T(n -2) + c.
T(n - 1) > T(n - 2)
T(n) >= 2T(n - 2)
I think T(n) is greater than or equal to 2T(n - 2).

---

$T(n-2) < T(n-1)$

Adding $T(n-1)$ both sides,

$\Rightarrow$ $T(n) < 2T(n-1)$

---

Okay.

---

Thank you