Question 1
Open practiceAnalyze the following two implementations of Fibonacci sequence and answer: What is the time complexity difference?
Implementation 1: Recursive
def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n-1) + fib_recursive(n-2)
Implementation 2: Dynamic Programming
def fib_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

For , which statement is most accurate?
A: Both have same complexity
B: Recursive is , DP is - DP is exponentially faster
C: Recursive is , DP is
D: Both are but DP uses more memory
E: Recursive is , DP is
F: The complexity depends on the input value, not the algorithm
Answer and explanation
Correct Answer: B — B: Recursive is $O(2^n)$, DP is $O(n)$ - DP is exponentially faster
Time Complexity Analysis
Recursive Implementation
The recursive version has exponential time complexity because:
- Each call branches into 2 more calls
- Many subproblems are recalculated multiple times
- The recursion tree has approximately nodes
Recurrence relation:
Solving this gives: where (golden ratio)
For practical purposes:
Dynamic Programming Implementation
The DP version has linear time complexity because:
- Single loop from 2 to n
- Each subproblem calculated exactly once
- Results stored and reused
Performance Comparison for n=40:
- Recursive: ~ = 1,099,511,627,744 operations (~1 trillion!)
- DP: 40 operations
Space Complexity:
- Recursive: due to call stack
- DP: for the array
Optimization Note: DP can be further optimized to 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.
