Recursion Computer Science Practice Sets

Computer ScienceHardData Structures Algorithms Time Complexity

Analyze 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]

Fibonacci Recursion Tree

For $n = 40$ , which statement is most accurate?

Both have same complexity $O(n)$

Recursive is $O(2^n)$ , DP is $O(n)$ - DP is exponentially faster

Recursive is $O(n^2)$ , DP is $O(n \log n)$

Both are $O(n^2)$ but DP uses more memory

Recursive is $O(n!)$ , DP is $O(2^n)$

The complexity depends on the input value, not the algorithm

Answer and explanation

Correct Answer: 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 $O(2^n)$ because:

Each call branches into 2 more calls
Many subproblems are recalculated multiple times
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:

Single loop from 2 to n
Each subproblem calculated exactly once
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.

Printing this content is disabled

Recursion in Computer Science

Time Complexity Analysis

Recursive Implementation

Dynamic Programming Implementation