...
/Optimizing the Fibonacci Numbers Algorithm
Optimizing the Fibonacci Numbers Algorithm
In this lesson, we will learn a better way to tabulate the Fibonacci numbers algorithm for better space complexity.
We'll cover the following...
Fibonacci numbers algorithm with tabulation
In the last lesson, we saw a bottom-up implementation of the Fibonacci numbers algorithm. We discussed how the time complexity of that algorithm was O(n), thanks to tabulation. However, due to tabulation, our space complexity also rose to O(n).
Do we really need this much space for this algorithm? Or can we do better by using our space smartly?