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);
}
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.
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!
