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?