Solving Fibonacci with an acceptable time complexity.

Write a function `fib(n)` that takes in a number as an argument. The function should return the n-th number of the Fibonacci sequence.

The first and second number of the sequence is one. To generate the second number of the sequence, we sum the previous two.

We must first look at the problem visually

fibonacci tree

The image shows that fib of 5 is the sum of fib of 4 and fib of 3. We can also see that fib of three shows up multiple times in this tree. If the input where much larger fib of larger numbers would also have multiples. So, we can cut the time complexity of this problem by placing this recuring fibs in a memo object. This is known as memoization. Please examine the following code.


const fib = (n, memo = {}) => {
    if (n in memo) return memo[n];
    if (n <= 2) return 1;
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
};