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

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 widely used in computer science and mathematics, often appearing in problems related to dynamic programming, recursion, and algorithm optimization.

Potential pitfalls include inefficient recursive solutions that have exponential time complexity and excessive space usage due to stack overflow or unnecessary storage.

Approach

To solve this problem, we can consider multiple approaches:

Naive Recursive Solution

The naive approach involves a simple recursive function:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

However, this approach has exponential time complexity O(2^n) and is highly inefficient for large values of n.

Dynamic Programming with Memoization

We can improve the naive approach by storing previously computed values:

int fib(int n) {
    int[] memo = new int[n + 1];
    return fib(n, memo);
}

int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

This approach reduces the time complexity to O(n) but uses O(n) space.

Optimized Iterative Solution

To achieve O(n) time complexity and O(1) space complexity, we can use an iterative approach with two variables:

int fib(int n) {
    if (n <= 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

This approach is both time and space efficient.

Algorithm

Here is a step-by-step breakdown of the optimized iterative algorithm:

Initialize two variables, prev and curr, to store the last two Fibonacci numbers, starting with 0 and 1.
Iterate from 2 to n, updating the variables to store the next Fibonacci number.
After the loop, curr will contain the nth Fibonacci number.

Code Implementation

public class Fibonacci {
    public static int fib(int n) {
        // Handle base cases
        if (n <= 1) return n;
        
        // Initialize the first two Fibonacci numbers
        int prev = 0, curr = 1;
        
        // Compute Fibonacci numbers iteratively
        for (int i = 2; i <= n; i++) {
            int next = prev + curr; // Calculate the next Fibonacci number
            prev = curr; // Update prev to the last Fibonacci number
            curr = next; // Update curr to the current Fibonacci number
        }
        
        // Return the nth Fibonacci number
        return curr;
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(fib(2)); // Output: 1
        System.out.println(fib(3)); // Output: 2
        System.out.println(fib(4)); // Output: 3
    }
}

Complexity Analysis

The time complexity of the optimized iterative solution is O(n) because we compute each Fibonacci number once. The space complexity is O(1) because we only use a constant amount of space to store 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.
Large values of n: Ensure the algorithm handles large inputs efficiently.

Testing

To test the solution comprehensively, consider a variety of test cases:

Simple cases: n = 0, n = 1, n = 2
Medium cases: n = 10, n = 20
Large cases: n = 50, n = 100

Use a testing framework like JUnit to automate the testing process.

Thinking and Problem-Solving Tips

When approaching such problems:

Understand the problem requirements and constraints.
Start with a simple solution and identify its limitations.
Optimize the solution step-by-step, considering time and space complexity.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to compute the nth Fibonacci number efficiently using an iterative approach in Java. We covered the problem definition, various approaches, algorithm breakdown, code implementation, complexity analysis, edge cases, and testing strategies. Understanding and solving such problems is crucial for developing strong algorithmic skills.

Additional Resources

For further reading and practice, consider the following resources: