Fibonacci Series with Dynamic Programming

Question

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 ?

Answer 1

$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.

Answer 2

It's both (up to a possible off-by-one error). If you look at the left-most branch of the recursion tree, it's labelled $f(n),ドル $f(n-1),ドル ..., so the number of levels of the tree is equal to the index of the Fibonacci number you're computing (plus or minus one, depending on where exactly you stop the recursion).

Answer 3

n-th number of Fibonacci series is : f(n) = f(n-1) + f(n-2) with f(0)=1 & f(1)=1 if we don't use Dynamic programming time complexity will be O(2^n) but if we use space of O(n) we can do it in O(n) ! We allocate an array A of size n; then we set A[0]=A[1]=1; now we calculates eazh A[i] i>2 by having A[i-1] and A[i-2] as below : A[i] = A[i-1] + A[i-2] so a for loop in O(n) computes f(n) !!