We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity reaches exponential time.
f(5) -> 2^0 / \ / \ f(4) f(3) -> 2^1 / \ / \ f(3) f(2) f(2) f(1) ->2^2 / \ f(2)f(1)............
Each recursive call consumes only O(1) time.
T(n) = 2^0 + 2^1 + 2^2.... (geometri series)
T(n) = (2^n - 1) / 2 - 1
T(n) = O(2^n)
In some places, it is written that n is size of the problem, but I think n is number of levels in recursion tree. Is n equal to size of the problem or number of recursion levels ?