Algorithms – Optimizing nth Fibonacci Number

Let me make it clear beforehand. Don’t misinterpret the heading. I am not going to talk about the Fibonacci optimization technique using memoization and DP where you  store the result of sub-problems to make the algorithm faster. That’s the old school optimization technique which has a time complexity of O(n) and an equivalent space complexity. There is an even better optimization technique which I came across in one of my graduate classes (where I am a student:D).  I will be talking about a new way of representing the Fibonacci series which will help us compute the results way faster than the other techniques.
Continue reading “Algorithms – Optimizing nth Fibonacci Number”