What will be we doing? |
So, you paid attention to complexity of Big-O Notation when it comes to Fibonacci algorithm, you would have noticed that it has colossal lag when it comes to execution. So what is the solution? There is one and it is called Memorized Fibonacci.
Here is our original Fibonacci function So With Memorized Fibonacci algorithm we will try and solve the issue by eliminating recalculation that is occurring and
In our fibMemo function we will have two parameters : index and cache. Index parameter will be our index of numbers in Fibonacci sequence and cache will be an array that will be stored in a memory. The bottom problem with our original Fibonacci sequence is the fact when you invoke a function and bring in a new number, the function begins to calculate from 0. Imagine you are on ground floor and you need to get to 7th floor. You hop on elevator and press 7 and you get to 7th floor. Now, you are on 7th floor and you need to get to 20th floor. You wont need to go to ground floor and press 20. You will pass by 7th floor. So the formula for this is O(n) = linear |