My Fibonacci problems solutions.

fib.md

The Fibonacci series is a numerical series where each item is the sum of the two previous items. It starts off like this: 0,1,1,2,3,5,8,13,21... Is usually used in white board interview to know if the candidate has some knowledge about algorithm and The notation.

One of the obvios solotion to solve the Fibonacci series problem is to use recursion, but the problem this is to deal with the maximum call stack problem:

Any recursive function use a base case and a recursive case, in Fibonacci this works like this: - base case: if n is 0 or 1 return n - recursive case: return fib(n - 1) + fib(n - 2)

     const fibRecursion = n => {
        if (n === 0 | n === 1)
            return n
        return fibRecursion(n - 1) + fibRecursion(n - 2)
    }

This works! But what is our time complexity?

Each call to our fib() function make more two calls, this cause a binary tree whoose heigth N, wich means the total number of nodes is O(2²). So our total runtime has a 'exponential cost' since the n is an exponent. Exponential cost is one of the worst scenarios, our function essentially get twice as big each time we add 1 to n.

How to solve this?

We can use common strategy of dynamic programming to solve this problem, the main solutions are Memoization and bottom-up. Above you can see this two in action.

• Memoization: ensure that a function doesn't run for the same inputs more than once by keeping a record of the inputs.

  function Memoization () {
    this.memo = {}
}

Memoization.prototype.fib = n => {

    // base cases
    if (n === 0 || n === 1) 
        return n

    // see if we've already calculated this
    if (this.memo.hasOwnProperty(n)) {
        console.log(`grabbing memo[ ${n} ]`)
        return this.memo[n]
    }

    console.log(`computing fib( ${n} )`)
    const result = this.fib(n - 1) + this.fib(n - 2)

    // memoize
    this.memo[n] = result

    return result
}

• Bottom-up: is to avoid recursion, this way we can save memory cost. Bottom-up algorithm start from begging while a recursive algorithm often start from the end and works backwards

  function fib(n) {

    // edge cases:
    if (n === 0 || n === 1)
        return n
    /**
     * we'll be building the fibonacci series from the bottom up
     * so we'll need to track the previous 2 numbers at each step
     **/
    let prevPrev = 0  // 0th fibonacci
    let prev = 1      // 1st fibonacci
    let current       // Declare current

    for (let i = 1; i < n; i++) {

        // Iteration 1: current = 2nd fibonacci
        // Iteration 2: current = 3rd fibonacci
        // Iteration 3: current = 4th fibonacci
        // To get nth fibonacci ... do n-1 iterations.
        current = prev + prevPrev
        prevPrev = prev
        prev = current
    }

    return current
}