Dynamic Programming with Fibonacci

dynFib.js

//More info: <https://thenewobjective.com/blog/2013/01/dynamic-programming-for-great-justice/>

// Imperative:  O(n) time, O(1) space
function fib(n){
    if(n < 2)
        return n;
 
    var f0 = 0, f1 = 1, f;
 
    for(var i = 1; i < n; i++){
        f  = f0 + f1;
        f0 = f1;
        f1 = f;
    }
    return f;
}

// O(φ) time, O(n^2) space
function fib(n){
    return n < 2 ? n : fib(n - 1) + fib(n - 2)
}


// dynamic programming (top down approach : memoization)
// O(n) time, O(n) space
function fib(n){
    return n < 2 ? n : fib.memo[n] || (fib.memo[n] = fib(n - 1) + fib(n - 2))
}
fib.memo = [];


// dynamic programming (bottom up approach : tabulation [also referred to as iteration?])
// O(n) time, O(1) space
function fib(n){
    function f(n0,n1,step){
        return step == n ? n1 : f(n1, n0 + n1, step + 1)
    }
    return f(0,1,1)
}

//Binet's formula
// O(1) time, O(1) space
function fib(n){
    var SQRT_5 = Math.sqrt(5), pow = Math.pow;
    return Math.round((pow(1 + SQRT_5,n) - pow(1 - SQRT_5,n))/(pow(2,n)*SQRT_5));
}