fib(2)
results 3(!) times?
Basically, if we just store the value of each index in a hash, we will avoid the computational time of that value for the next N
times. This change will increase the space complexity of our new algorithm to O(n)
but will dramatically decrease the time complexity to 2N
which will resolve to linear time since 2 is a constant O(n)
.
There’s just one problem: With an infinite series, the memo array will have unbounded growth. Eventually, you’re going to run into heap size limits, and that will crash the JS engine. No worries though. With Fibonacci, you’ll run into the maximum exact JavaScript integer size first, which is 9007199254740991
. That’s over 9 quadrillion, which is a big number, but Fibonacci isn’t impressed. Fibonacci grows fast. You’ll burst that barrier after generating only 79 numbers.
function fibonacci(num, memo) { memo = memo || {}; if (memo[num]) return memo[num]; if (num <= 1) return 1; return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);}