dilluns, 30 de juliol de 2012

Dynamic programming - The Fibonacci numbers example

Extracted from slides of Chandra Chekuri about Dynamic programming

In this post we will find an introduction to dynamic programming, using as a example a classic problem. In the second part there is a cost analysis of the proposed algorithms in relation with the input size.

Fibonacci numbers are defined by the recurrence

F(0) = 0, F(1) = 1, and F(n) = F(n-1)+F(n-2) for n >=2

The first idea when we want to compute the Fibonacci number for a given n is to use a recursive algorithm like the following:

int fibonacci(int n) {
  if n == 0 return 0;
  if n == 1 return 1;
  return fibonacci(n-1) + fibonacci(n-2);

The running time of this algorithm is the following:  
If T(n) is the number of additions of fibonacci(n), then T(n) = T(n-1)+T(n-2) + 1, with T(0) = T(1) = 0, roughly the same as fibonacci(n).

The algorithm does exponential in n additions: T(n) = k^n.

Can we do better?

An iterative solution is the following:

int fibonacci(int n) {
  if n == 0 return 0;
  if n == 1 return 1;

  F[0] = 0; F[1] = 1;
  for (int i = 2; i <= n; i++) {
    F[i] = F[i-1] + F[i-2];
  return F[n];

The running time of the algorithm is O(n) additions.

What is the difference?
  • Recursion algorithm is computing the same numbers again and again.
  • Iterative algorithm is storing computed values and building bottom-up the final value. It uses memoization.
Dynamic programming consists in finding a recursion that can be effectively/efficiently memoized.

Leads to a polynomial time algorithm if the number of sub-problems is polynomial in input size.

And now an important question.

Is the iterative algorithm a polynomial time algorithm? Does it take O(n) time?

Let's examine it:
  • Input is n, and hence input size is Θ(log n).
  • Output is fibonacci(n), and output size is Θ(n). Why? Because of the size of the numbers being added.
  • Hence output size is exponential in input size so no polynomial time algorithm is possible!
  • Running time of the iterative algorithm: Θ(n) additions, but the number sizes are O(n) bits long! Hence total time is O(n^2), in fact Θ(n^2).
  • Running time of the recursive algorithm: O(k^n), doubly exponential in input size!