The optimal method for computing the Fibonacci sequence using JavaScript

Question

The optimal method for computing the Fibonacci sequence using JavaScript

Improving my skills in optimizing algorithms and understanding big-o notation is a priority for me.

I devised the following function to compute the n-th Fibonacci number. It works well for higher inputs, but I wonder how I can enhance it. What are the downsides of calculating the Fibonacci sequence in this manner?

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 suspect that my time complexity is O(n), while the space complexity could be O(n^2) due to the array creation. Is my analysis correct?

javascript algorithm big-o fibonacci

Answer 1

Answer №1

By avoiding the use of an Array, you can optimize memory usage and reduce the number of .push calls needed

function fibonacci(n) {
    var first = 0, second = 1, result;
    if (n < 3) {
        if (n < 0) return fibonacci(-n);
        if (n === 0) return 0;
        return 1;
    }
    while (--n)
        result = first + second, first = second, second = result;
    return result;
}

Answer 2

By avoiding the use of an Array, you can optimize memory usage and reduce the number of .push calls needed

function fibonacci(n) {
    var first = 0, second = 1, result;
    if (n < 3) {
        if (n < 0) return fibonacci(-n);
        if (n === 0) return 0;
        return 1;
    }
    while (--n)
        result = first + second, first = second, second = result;
    return result;
}

Answer 3

Answer №2

Fibonacci Performance Test:

    var memo = {};
    var countInteration = 0;
    var fib = function (n) {
        if (memo.hasOwnProperty(n)) {
            return memo[n];
        }
        countInteration++;
        console.log("Iteration = " + 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`

Answer 4

Fibonacci Performance Test:

    var memo = {};
    var countInteration = 0;
    var fib = function (n) {
        if (memo.hasOwnProperty(n)) {
            return memo[n];
        }
        countInteration++;
        console.log("Iteration = " + 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`

The optimal method for computing the Fibonacci sequence using JavaScript

Answer №1

Answer №2

Similar questions

The client continues to request the file through the REST API

ReactJS aligns buttons to the right

Various settings in JQuery UI Slider

Get around operator precedence in JavaScript

What are the steps to take in order to successfully deploy an Express server on GitHub Pages?

Create a new array containing the keys from an array of objects

Is there a more efficient method for translating arrays between JavaScript and PHP?

Using Material-UI in a project without the need for create-react-app

The dilemma between Nuxt Js global CSS and Local CSS

How to retrieve a refined selection of items

Implementing sound playback within an AJAX response

The websocket server implemented in Node.js with the use of the "ws" library is exhibiting a peculiar behavior where it disconnects clients at random intervals,

Can jQuery Autocomplete function without stopping at white spaces?

What is the reason for calling Proxy on nested elements?

Unable to get Discord.js sample code functioning correctly

Setting up Babel to effectively function across multiple directories

Chunk loading in IE 11 has encountered an error

After reaching the character limit, errors occur due to data being sent through Ajax requests on keyup

A guide on updating object values within an array using map in React

Twitter typeahead not functioning properly when used in conjunction with ajax requests