Fibonacci Series with Dynamic Programming 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)    -&gt; 2^0
            /    \
           /      \
          f(4)    f(3)   -&gt; 2^1 
         /   \    /   \
       f(3) f(2) f(2) f(1) -&gt;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 ?
$n$ is the index of the Fibonacci number you're computing. For example, the sixth Fibonacci number, $f(6)$, is equal to 8.

If we assume that function calls take constant time and we are using your model, then it's clear that the number of calls, $C(n)$, to compute the $n$-th Fib will be given by 
$$C(n)=C(n-1)+C(n-2)$$
with $C(0)$ and $C(1)$ both being 1.

Hmm. That recurrence is almost exactly the recurrence for the Fibs, just shifted by a place, so we have $C(n)=f(n+1)$. In other words, the asymptotic growth of $C(n)$ is the same as the Fibs themselves.