Fibonacci Number in Python with O(n) Time Complexity and O(1) Space Complexity

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 deep recursion stacks.

Approach

To solve this problem, we can consider several approaches:

Naive Recursive Solution

The naive approach involves a simple recursive function:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

However, this approach has exponential time complexity, O(2^n), due to repeated calculations of the same subproblems.

Dynamic Programming with Memoization

We can optimize the recursive approach using memoization to store previously computed values:

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

This reduces the time complexity to O(n) but still uses O(n) space for the memoization table.

Iterative Solution with O(1) Space

The most efficient approach is to use an iterative solution that only keeps track of the last two Fibonacci numbers:

def fibonacci(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        next_fib = prev + curr
        prev = curr
        curr = next_fib
    return curr

This approach runs in O(n) time and uses O(1) space, meeting the problem's constraints.

Algorithm

Here's a step-by-step breakdown of the 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

Below is the Python code for the iterative solution:

def fibonacci(n):
    # Handle base cases
    if n <= 1:
        return n
    
    # Initialize the first two Fibonacci numbers
    prev, curr = 0, 1
    
    # Compute Fibonacci numbers iteratively
    for _ in range(2, n + 1):
        next_fib = prev + curr  # Calculate the next Fibonacci number
        prev = curr  # Update prev to the current Fibonacci number
        curr = next_fib  # Update curr to the next Fibonacci number
    
    return curr  # Return the nth Fibonacci number

Complexity Analysis

The time complexity of the 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 for the variables prev and curr.

Edge Cases

Consider the following edge cases:

n = 0: The function should return 0.
n = 1: The function should return 1.

The provided code handles these cases by checking if n <= 1 at the beginning.

Testing

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

Simple cases: n = 0, n = 1, n = 2
Small values: n = 5, n = 10
Large values: n = 50, n = 100

Use a testing framework like unittest or pytest to automate the testing process.

Thinking and Problem-Solving Tips

When approaching problems like this, consider the following tips:

Understand the problem requirements and constraints.
Start with a simple, naive solution to understand the problem better.
Optimize the solution by identifying and eliminating redundant calculations.
Consider both time and space complexity when evaluating solutions.

Conclusion

In this blog post, we discussed how to compute the nth Fibonacci number efficiently using an iterative approach with O(n) time complexity and O(1) space complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science and programming.

Additional Resources

For further reading and practice, consider the following resources: