Feb 3, 2017
Day 34 - Fibonacci, final optimization of bottom up
Yesterday, we looked at a bottom up approach solving fibonacci numbers that runs in O(n) time. That approach stores all previous numbers in memory, so if we were looking at Fib(241), we’d have to store 241 numbers. But, realizing that we only really need to store the two previous numbers to calculate the current number, we can save space by only saving a reference to the two previous values. Thus it can run in O(n) time, and use constant space by only storing 2 integers at any given time.
