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

Tips for verifying that a file has not been selected in Croppie

activating javascript function in rails when the page reloads

What is the best way to determine the quantity of elements received from an ajax request?

How to switch the code from using $.ajax() to employing $.getJSON in your script

The process of incorporating the dymo.framework into an Angular project

Leveraging v-for within a component that incorporates the <slot/> element to generate a versatile and interactive Tab menu

Retrieving values of checked boxes in a table using JavaScript

``Next.js allows you to nest components within a component to create routing functionalities

Revitalizing and rerouting page upon button click

Updating switch data on click using Vuejs: A step-by-step guide

Can't get className to work in VueJS function

Make a quick call to the next function within the error handling module for a

Gulp does not generate any new folders

Using React to access the properties of objects within an array that has been dynamically mapped

Utilizing socket.io to access the session object in an express application

Ways to detect the use of vue.js on a webpage without relying on vue-devtools

Methods for resolving a ViewStyle typescript issue in react native

What method can I use in pure Javascript to identify which day the week begins on, either Monday or Sunday, based on the

A tool that enhances the visibility and readability of web languages such as HTML, PHP, and CSS

The function Amplify.configure does not exist