« Time complexity for Fibonacci function

Time complexity for Fibonacci function

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

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

...

Solving above equations will be pretty difficult so lets draw recursion graph and lets try to get out time complexity from there.

Each of the steps does nothing. They just call further steps and does some k total work. So all the steps will do some k work. In total we have 2ⁿ steps. So total time complexity will be k(2ⁿ).

T(n) = O(2ⁿ)