The Fibonacci Series.

In this post, I’ll show how to solve the Fibonacci Series algorithm question with two different solutions and improve the time complexity of one of the answers (recursive).

—Directions of the questions:

Print out the n-th entry in the Fibonacci series. The Fibonacci series is an ordering of numbers where each number is the sum of the preceding two. For example, the sequence [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] forms the first ten entries of the Fibonacci series. Example: fib(4) === 3

1. Iterative Solution:

function fib(n) {
  const result = [0, 1];
   for (let i = 2; i <= n; i++){
   const a = result[i - 1];
   const b = result[i - 2];
  result.push(a+b);
  };
 return result[result.length-1]
};

If we think about this solution’s run complexity, we can see a linear complexity O(n). It a for loop where the results have to run just once through the loop.

2. Recursive Solution:

function fib(n) {
   if ( n < 2) {
   return n;
   };
   return fib(n - 1) + fib(n - 2);
}

Calling this function recursively would take a lot of time. It’s an exponential time complexity in terms of time complexity — O(2^n). Since we keep calling the fib function inside the fib function repeatedly, it can significantly slow down the runtime of it.

When we try to evaluate fib(5), we notice that we repeatedly try to find the Fibonacci number at indices 0, 1, 2 and 3 on different branches. This is known as redundant computation.

How can we improve the runtime of this solution?

By using a memoization. Memoization is an optimization technique that speeds up applications by storing the results of expensive function calls and returning the cached result when the same inputs are supplied again.

We will call a generic memoization function with a slow version of Fibonacci, and memoized function will return a fast version of the Fibonacci function. Before calling the fib function, let’s create a data store/cache object (memoize function). The key is that we would call the same arguments (in this example it’s a number) as we would call for the slowFib function.

function memoize(fn) {
   const cache={}; // creating a record of all of the previous calls of the slowFib function and store it
return function(...args) { // returning an anonymous function -                     // that is or fib function in the last line of code with arguments //that received to out slowFin function, example: fib(5)
     if (cache[args]) {
       return cache[args];
     };
     const result = fn.apply(this, args);
     cache[args] = result;
     return result;
   };
};
function slowFib(n) {
  if ( n < 2) {
  return n;
  };
  return fib(n - 1) + fib(n - 2);
};
const fib = memoize(slowFib);

In conclusion, with memoization, when a function is provided input, it does the required computation and stores the result to cache before returning the value. If this same input is ever received in the future, it wouldn’t have to do it over and over again. It would simply provide the answer from the cache(memory).

Understanding Memoization In JavaScript