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?

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?

• javascript
• algorithm
• big-o
• fibonacci

• I suggest you post this on: codegolf.stackexchange. – Halcyon Commented Apr 30, 2015 at 16:56
• or maybe: codereview.stackexchange. – Matt Burland Commented Apr 30, 2015 at 16:58
• I wrote an article on the Fibonacci sequence recently in the context of interview questions, focusing on plexity. You might find this useful looking at some of the implementations and their characteristics. growingwiththeweb./2013/09/algorithm-fibonacci-sequence.html – Daniel Imms Commented Apr 30, 2015 at 17:01
• Why would ECMAScript/JavaScript be special? – greybeard Commented Sep 17, 2016 at 13:02

2 Answers 2

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

Performance Fibonacci:

    var memo = {};
    var countInteration = 0;
    var fib = function (n) {
        if (memo.hasOwnProperty(n)) {
            return memo[n];
        }
        countInteration++;
        console.log("Interation = " + n);
        if (n == 1 || n == 2) {
            result = 1;
        } else {
            result = fib(n - 1) + fib(n - 2);
        }
        memo[n] = result;
        return result;
    }
    //output `countInteration` = parameter `n`