Fibonacci Problem

Understanding the Problem:

The Fibonacci sequence is defined recursively:

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

A naive recursive approach leads to exponential time complexity (O(2^n)) due to redundant calculations. We can drastically improve this.

Optimized Solutions:

Iterative Approach (Linear Time Complexity)

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci_iterative(10))  # Output: 55

• Explanation: We directly compute successive Fibonacci numbers in a loop, storing only the previous two values to calculate the next one. This has O(n) time complexity.

Dynamic Programming with Memoization (Linear Time Complexity)

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    result = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    memo[n] = result
    return result

print(fibonacci_memoization(10))  # Output: 55

• Explanation: We store the results of calculated Fibonacci numbers to avoid redundant recalculations. This also achieves O(n) time complexity, especially effective when you need multiple Fibonacci numbers in the sequence.

Why These Are Optimal:

These solutions have a linear time complexity of O(n), meaning the execution time grows proportionally to the input size (n). This is the best achievable time complexity for generating Fibonacci numbers, as you need to calculate each number in the sequence.

Key Points:

• The iterative approach is often slightly faster in practice due to less function call overhead.
• Dynamic Programming is more elegant for scenarios where you need to calculate various Fibonacci numbers repeatedly.