We will talk a little bit more about how to compute Fibonacci numbers and in particular today what we are going to do is we are going to show you how to produce a very simple algorithm that computes these things correctly. On the other hand, we are going to show that this algorithm is actually very slow and talk a little bit about how to analyse that.
So, let us take a look at the definition again. The zero Fibonacci number is zero. The first Fibonacci number is one and from there after each Fibonacci number is the sum of the previous two. Now these grow pretty rapidly and what we would like to do is have an algorithm to compute them. So, let us take a look at how we might do this.
Well, there is a pretty easy way to go about it given the definition. So, if n is zero, we are supposed to return zero and if n is one, we are supposed to return one. So, we can just start with the case that says if n is at most one, we are going to return n. Otherwise what are we supposed to do? Otherwise we are supposed to return the sum of the n minus first and n minus second Fibonacci numbers so we can just compute those two recursively, add them together and return that. So, this gives a very simple algorithm four lines long that basically took the definition of our problem and turned it into an algorithm that correctly computes the thing it is supposed to.
Good for us. We have an algorithm and it works. However, we care a lot more than just does our algorithm work. We also want to know if it is efficient. We would like to know how long this algorithm takes to run and there’s sort of a rough approximation to this. We are going to let T of n denote the number of lines of code that are executed by this algorithm on input n. So, to count this is actually not very hard. So, if n is at most one, the algorithm checks the if case, goes to the return statement and that is two lines of code, not so bad. If n is at least two, we go to the if case, we go to the else condition and then run a return statement. So that is three lines of code. However, in this case we also need to recursively compute the n minus first and n minus second Fibonacci numbers, so we need to add to that, however many lines of code those recursive calls take. So, all in all we have a nice recursive formula for T of n it is two as long as n is at most one and otherwise it’s equal to T of n minus one plus T of n minus two plus three. So a nice recursive formula.
Now if you look at this formula for a little bit, you will notice that it looks very similar to the original formula we used to define the Fibonacci number. Each guy was more or less the sum of the previous two. And in fact, from this you can show pretty easily that T of n is at least the nth Fibonacci number for all n and this should be bringing some warning bells because we know that the Fibonacci numbers get very very very large. So, T of n must as well. In fact, T of 100 is already 1.77 times 10 to the 21. 1.77 sextillion. This is a huge number.
Now supposed we were running this program on a computer that executed a billion lines of code a second, run it at gigahertz, it would still take us about 56,000 years to complete this computation. Now I do not have 56,000 years to wait for my computation to finish. You probably do not either so this really is somehow not acceptable if we want to compute Fibonacci numbers of any reasonable size. So, what we would really like is we would like a better algorithm!
We should now talk a little bit about why this algorithm is so slow and to see that maybe the clearest way to demonstrate it is to look at all the recursive calls this algorithm needs in order to compute its answer. So, if we want to compute the nth Fibonacci number, we need to make recursive calls to compute the n minus first and n minus second Fibonacci numbers.
To compute the n minus first, we need the n minus second and n minus third. To compute the n minus second, we need the n minus third and n minus fourth and it just keeps going on on from there. We get this big tree of recursive calls. Now if you will look at this tree a little bit loser, it looks like we are doing something a little bit silly. We are computing Fn minus three, three separate times in this tree and the way that our algorithm works, every time we are asked to compute it, since it’s a new recursive call, we compute the whole thing from scratch.
We recompute Fn minus four, and Fn minus five and then add them together and get our answer and this sort of computing the same thing over and over again that’s really slowing us down and to make it even more extreme, let’s blow up the tree a little bit more.
Fn minus four actually gets computed these five separate times by the algorithm and as you keep going down more and more and more times, you are just computing the same thing over and over again and this is really the problem with this particular algorithm.