Fibonacci in JavaScript

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate and return F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.

Understanding the Problem

The core challenge of this problem is to compute the nth Fibonacci number efficiently. The Fibonacci sequence is a classic example in computer science and has applications in various fields such as mathematics, computer algorithms, and even financial models. A common pitfall is using a naive recursive approach, which has exponential time complexity and is not feasible for large values of n.

Approach

To solve this problem efficiently, we need to avoid the naive recursive approach and instead use an iterative approach that runs in O(n) time and uses O(1) space.

Naive Solution

The naive solution involves using recursion:

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

While this solution is simple, it has exponential time complexity O(2^n) and is not suitable for large values of n.

Optimized Solution

We can optimize the solution by using an iterative approach with two variables to store the last two computed Fibonacci numbers. This approach runs in O(n) time and uses O(1) space.

Algorithm

1. Initialize two variables, prev and curr, to store the last two Fibonacci numbers. Set prev to 0 and curr to 1.

2. Iterate from 2 to n, updating the variables as follows:

Compute the next Fibonacci number as the sum of prev and curr.
Update prev to the value of curr.
Update curr to the value of the next Fibonacci number.

3. After the loop, curr will contain the nth Fibonacci number.

Code Implementation

function fibonacci(n) {
    // Handle base cases
    if (n === 0) return 0;
    if (n === 1) return 1;

    // Initialize the first two Fibonacci numbers
    let prev = 0;
    let curr = 1;

    // Iterate from 2 to n
    for (let i = 2; i <= n; i++) {
        // Compute the next Fibonacci number
        let next = prev + curr;
        // Update prev and curr
        prev = curr;
        curr = next;
    }

    // Return the nth Fibonacci number
    return curr;
}

Complexity Analysis

The time complexity of this approach is O(n) because we iterate from 2 to n. The space complexity is O(1) because we only use a constant amount of extra space for the variables prev and curr.

Edge Cases

Consider the following edge cases:

n = 0: The output should be 0.
n = 1: The output should be 1.

The algorithm handles these cases explicitly at the beginning.

Testing

To test the solution comprehensively, consider the following test cases:

n = 0: The output should be 0.
n = 1: The output should be 1.
n = 2: The output should be 1.
n = 3: The output should be 2.
n = 10: The output should be 55.
n = 20: The output should be 6765.

These test cases cover small values, typical values, and larger values of n.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem and constraints thoroughly.
Start with a naive solution to get a basic understanding.
Identify inefficiencies in the naive solution and think about how to optimize it.
Consider using iterative approaches to reduce time and space complexity.
Test your solution with a variety of test cases, including edge cases.

Conclusion

In this blog post, we discussed how to compute the nth Fibonacci number efficiently using an iterative approach. We covered the problem definition, naive and optimized solutions, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice problems related to the Fibonacci sequence, consider the following resources:

Fibonacci Number in O(n) Time and O(1) Space using JavaScript