Printing this content is disabled

Time Complexity Analysis

Recursive Implementation

The recursive version has exponential time complexity $O(2^n)$ because:

1. Each call branches into 2 more calls
2. Many subproblems are recalculated multiple times
3. The recursion tree has approximately $2^n$ nodes

Recurrence relation: $T(n) = T(n-1) + T(n-2) + O(1)$

Solving this gives: $T(n) = O(\phi^n)$ where $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ (golden ratio)

For practical purposes: $O(2^n)$

Dynamic Programming Implementation

The DP version has linear time complexity $O(n)$ because:

1. Single loop from 2 to n
2. Each subproblem calculated exactly once
3. Results stored and reused

Performance Comparison for n=40:

• Recursive: ~$2^{40}$ = 1,099,511,627,744 operations (~1 trillion!)
• DP: 40 operations

Space Complexity:

• Recursive: $O(n)$ due to call stack
• DP: $O(n)$ for the array

Optimization Note: DP can be further optimized to $O(1)$ space by keeping only last two values:

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

Conclusion: DP is exponentially faster than naive recursion for Fibonacci.