Fibonacci Numbers | Dynamic Programming

The Fibonacci Numbers are described by the recurrence relation

F(n) = F(n-1) + F(n-2) where F(0) = 0 and F(1) = F(1)

If you were told to write a program to find the Nth Fibonacci Number, you would have probably written the following recursive procedure if you didn’t know dynamic programming.

procedure FIND-FIBONACCI-NUMBER(N)   if N<2     return N   else     return FIND-FIBONACCI-NUMBER(N-1)+FIND-FIBONACCI-NUMBER(N-2)

The above procedure is correct and very simple to implement. So what is the problem? Why should you use dynamic programming?

I will illustrate my point with the help of the following table.

Time Taken to execute for different values of N

N	Naive Method	Dynamic Programming
The value indicated is in milliseconds and 0 implies negligible time.
The values will be different for different machines.
10	0	0
20	2	0
30	16	0
40	1882	0
50	302536	0

The above table clearly shows that the execution time for the naive method increases dramatically for small increases in value of N. The reason for this is that the naive method runs in exponential timewhereas the dynamic programming method runs in linear time!

Next time you get a Time Limit Exceeded (TLE) on CodeChef (or other programming sites), don’t go around complaining on the forum that the program is running fine on your computer. Test your program for large values of N to check whether it runs efficiently or not. If it doesn’t then it means you have to change the technique used to solve the problem.

I am not going to go into the details of dynamic programming as a lot of excellent material for the topic is already available. My objective was to show you the power of dynamic programming to entice you to learn it!.