Optimizing the Fibonacci Numbers Algorithm
Explore how to optimize the Fibonacci numbers algorithm by applying bottom-up dynamic programming and tabulation. Understand how to reduce space usage by storing only the last two Fibonacci numbers, improving space complexity from O(n) to O(1). Gain insights in state management for efficient algorithm design.
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?
Space complexity from O(n) to O(1)
To evaluate any Fibonacci number, we need the preceding two Fibonacci numbers. Nothing else. ...