MattDionis - 9 months ago 63

Javascript Question

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;
}
```

Source (Stackoverflow)