MattDionis MattDionis - 2 months ago 17
Javascript Question

Most efficient way to calculate Fibonacci sequence in Javascript

I'm attempting to get better with optimizing algorithms and understanding big-o, etc.

I threw together the below function to calculate the n-th Fibonacci number. This works (for a reasonably high input). My question is, how can I improve this function? What are the drawbacks of calculating the Fibonacci sequence this way?

function fibo(n) {

var i;
var resultsArray = [];

for (i = 0; i <= n; i++) {
if (i === 0) {
resultsArray.push(0);
} else if (i === 1) {
resultsArray.push(1);
} else {
resultsArray.push(resultsArray[i - 2] + resultsArray[i - 1]);
}
}

return resultsArray[n];
}


I believe my big-o for time is O(n), but my big-o for space is O(n^2) due to the array I created. Is this correct?

Answer

If you don't have an Array then you save on memory and .push calls

function fib(n) {
    var a = 0, b = 1, c;
    if (n < 3) {
        if (n < 0) return fib(-n);
        if (n === 0) return 0;
        return 1;
    }
    while (--n)
        c = a + b, a = b, b = c;
    return c;
}