two_fibonacci.js

/**
 * Fibonacci
 * 
 * 1, 1, 2, 3, 5, 8, 13, 21, 34
 * 
 * fibonacci = O(n^2) - exponential
 * fibMemo = O(n) - linear
 */

/** O(n^2) **/
const fibonacci = position => {
  if (position < 3) { 
    return 1
  }

  return fibonacci(position - 1) + fibonacci(position - 2) 
}

/** O(n) **/
const fibMemo = (position, cache = []) => {
  if (cache[position]) return cache[position]
  if (position < 3) return 1

  cache[position] = fibMemo(position - 1, cache) + fibMemo(position - 2, cache) 

  return cache[position]
}

console.time('Time for all');

for (let i = 0; i <= 500 ; i++ ) {
  console.time(`Time for ${i}`);
  console.log(`Fibo(${i}) = ${fibMemo(i, [])}`)
  console.timeEnd(`Time for ${i}`)
}

console.timeEnd('Time for all') // Time for all: 168.497ms