MattDionis - 1 year ago 135
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?

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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download