Optimising the Fibonacci sequence generating algorithm
I guess…
We all know the famous Fibonacci sequence, i.e.
0 1 1 2 3 5 8 13 21 34 55 ...where each term is simply equal to the sum of its previous 2 terms. Simple right? It is also a commonly used method to teach recursion in any programming language guide. The algorithm stated in those guides is always this horrible thing:
But how is this horrible at all?! This is so easy and simple!
Simple it may be, good it is not. Let me show you how. Due to the recursion in this algorithm, a lot of the computations are repeated. If you look at this tree representing recursive function calls, you can clearly see the same function calls multiple times. This is not acceptable. It leads to longer computation times and wastage of resources.
The time complexity of this naive algorithm turns out to be 2^n, looking at the graph below comparing the various Big-O time complexities, we can conclude that this algorithm is clearly useless for large numbers.
“That’s cool and all, what can you do about it?”
Simple, we stop the repeating function calls. One method to do this is memoisation. What is that, you ask?
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
So basically, we’ll store the previous terms of the Fibonacci sequence to calculate the further terms. We can do so using a simple array. Here’s the simple Python code to do so:
The time complexity for this algorithm turns out to be O(n), which is fairly good, considering how bad the previous one was. One problem with this though is you need extra memory to store the terms in an array. I encourage you to find a solution for that.
Can you also find an algorithm for generating a Fibonacci sequence using matrix exponentiation?
