Get the nth Fibonacci number in O(n) time and O(1) space complexity.

1.	Get the nth Fibonacci number in O(n) time and O(1) space complexity.
Answer» //Javascriptfunction fib(n){ let [x, y] = [0, 1] while (n > 0){ [x, y] = [y, x + y] n -= 1 } return x} This SOLUTION has a linear time complexity of O(n) and a constant space complexity of O(1). The number of loops required to determine the nth fib number will STILL increase linearly as n increases, but as we extend the sequence out, we are OVERRIDING the previous NUMBERS in the sequence, KEEPING the space complexity constant for any input n. It is often referred to as the Iterative Top-Down Approach.

Answer»

//Javascriptfunction fib(n){ let [x, y] = [0, 1] while (n > 0){ [x, y] = [y, x + y] n -= 1 } return x}

This SOLUTION has a linear time complexity of O(n) and a constant space complexity of O(1). The number of loops required to determine the nth fib number will STILL increase linearly as n increases, but as we extend the sequence out, we are OVERRIDING the previous NUMBERS in the sequence, KEEPING the space complexity constant for any input n. It is often referred to as the Iterative Top-Down Approach.

Discussion

No Comment Found

Related InterviewSolutions

What is the use of a CSS preprocessor? When should a pre-processor be utilised in a project, according to you?
Describe the main differences between the LocalStorage and SessionStorage objects in context to HTML.
What makes a block-level element different from an inline element in HTML?
What do you understand about RAID in context to Project Management?
Explain the Project Management Life Cycle method in context to Project Management.
What is EUCALYPTUS in cloud computing? List some of its functionalities.
What are the benefits of Hybrid Clouds in Cloud Computing?
How do the commands DROP, TRUNCATE, and DELETE differ in SQL?
What are the advantages and disadvantages of indexing in DBMS?
What are the different types of Shells in Linux?