DP vs Recursion vs Greedy Choosing the Right Tool in DSA Python - Complexity Comparison

Time Complexity: DP vs Recursion vs Greedy Choosing the Right Tool

O(2^n) for recursion, O(n) for DP and greedy

Understanding Time Complexity

Choosing between dynamic programming, recursion, and greedy methods affects how fast a solution runs.

We want to know how the time needed grows as the problem size gets bigger.

Scenario Under Consideration

Analyze the time complexity of these three approaches solving the same problem.

# Recursive Fibonacci (simple recursion)
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# Dynamic Programming Fibonacci (memoization)
def fib_dp(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_dp(n-1, memo) + fib_dp(n-2, memo)
    return memo[n]

# Greedy approach (not suitable here, but example)
def fib_greedy(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
    

These functions calculate Fibonacci numbers using recursion, dynamic programming, and a greedy-like iterative method.

Identify Repeating Operations

Look at what repeats in each method.

• Recursive: Calls itself twice for each number, many repeated calculations.
• Dynamic Programming: Calls itself once per number, stores results to avoid repeats.
• Greedy (Iterative): Loops once from 0 to n, updating values step-by-step.
• Dominant operation: Number of function calls or loop iterations depending on method.

How Execution Grows With Input

As n grows, the work changes differently for each method.

Input Size (n)	Recursive Calls	DP Calls	Greedy Iterations
10	177	19	10
100	O(2^100) (huge)	199	100
1000	O(2^1000) (impossible)	1999	1000

Recursive grows very fast (doubling calls), DP and greedy grow linearly with n.

Final Time Complexity

Time Complexity: O(2^n) for recursion, O(n) for DP and greedy

Recursive method takes exponentially more time, while DP and greedy scale linearly as input grows.

Common Mistake

[X] Wrong: "Recursion is always slow and should be avoided."

[OK] Correct: Recursion can be efficient if combined with memoization (DP), reducing repeated work.

Interview Connect

Understanding these differences helps you pick the right approach and explain your choice clearly in interviews.

Self-Check

"What if we removed memoization from the DP approach? How would the time complexity change?"

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Brute Force

B. Greedy Algorithm

C. Dynamic Programming

D. Simple Recursion without memoization

Solution

1. Step 1: Understand problem properties

   Overlapping subproblems mean the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller parts.

2. Step 2: Match approach to properties

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for these properties.

3. Final Answer:

   Dynamic Programming -> Option C

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when problem needs global optimization
• Using simple recursion causing repeated calculations
• Confusing brute force with efficient methods

2. Which of the following Python function definitions correctly implements a recursive Fibonacci function?

easy

A. def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2)

B. def fib(n): for i in range(n): return fib(i-1) + fib(i-2)

C. def fib(n): while n > 1: n -= 1 return n

D. def fib(n): return n + fib(n-1)

Solution

1. Step 1: Check base case and recursion

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) correctly returns n if n <= 1, else calls fib(n-1) + fib(n-2).

2. Step 2: Verify other options

   Options B, C, and D have syntax or logic errors: B uses for loop wrongly, C uses while without recursion, D causes infinite recursion.

3. Final Answer:

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) -> Option A

4. Quick Check:

   Correct recursive base and calls = def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) [OK]

Hint: Base case + two recursive calls = correct Fibonacci recursion [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursion incorrectly
• Wrong return statements inside recursion

3. What is the output of the following code?

def max_sum(arr, n):
    if n == 0:
        return 0
    elif n == 1:
        return arr[0]
    else:
        return max(max_sum(arr, n-1), max_sum(arr, n-2) + arr[n-1])

print(max_sum([3, 2, 7, 10], 4))

medium

A. 13

B. 17

C. 20

D. 10

Solution

1. Step 1: Understand function logic

   max_sum returns max sum of non-adjacent elements from first n elements.

2. Step 2: Trace calls for n=4

   max_sum(arr,4) = max(max_sum(arr,3), max_sum(arr,2) + arr[3]) max_sum(arr,3) = max(max_sum(arr,2), max_sum(arr,1) + arr[2]) max_sum(arr,2) = max(max_sum(arr,1), max_sum(arr,0) + arr[1]) Calculate bottom-up: max_sum(arr,0)=0 max_sum(arr,1)=3 max_sum(arr,2)=max(3,0+2)=3 max_sum(arr,3)=max(3,3+7)=10 max_sum(arr,4)=max(10,3+10)=13

3. Final Answer:

   13 -> Option A

4. Quick Check:

   Max sum non-adjacent = 13 [OK]

Hint: Trace recursion bottom-up for max sum non-adjacent [OK]

Common Mistakes:

• Adding adjacent elements mistakenly
• Confusing indices in recursion
• Ignoring base cases

4. The following code tries to solve the coin change problem using recursion but has an error. What is the error?

def coin_change(coins, amount):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    count = 0
    for coin in coins:
        count += coin_change(coins, amount - coin)
    return count

print(coin_change([1, 2], 3))

medium

A. It does not handle negative amounts correctly

B. It counts duplicate combinations multiple times

C. It misses base case for amount == 1

D. It uses iteration instead of recursion

Solution

1. Step 1: Analyze recursion logic

   The function counts ways to make amount by subtracting coins recursively.

2. Step 2: Identify counting duplicates

   Because it tries all coins at each step without order control, it counts same combinations in different orders multiple times.

3. Final Answer:

   It counts duplicate combinations multiple times -> Option B

4. Quick Check:

   Duplicates counted due to unordered recursion [OK]

Hint: Unordered recursion counts duplicates; use order or DP to fix [OK]

Common Mistakes:

• Assuming base cases are missing
• Confusing negative amount handling
• Thinking iteration replaces recursion

5. You want to find the minimum number of coins needed to make a given amount using coin denominations [1, 3, 4]. Which approach is best and why?

hard

A. Brute force trying all combinations without optimization

B. Simple recursion without memoization for clarity

C. Greedy algorithm because always picking largest coin works

D. Dynamic Programming to store and reuse subproblem results

Solution

1. Step 1: Understand problem requirements

   We want minimum coins to make amount, which requires checking all combinations to find optimal.

2. Step 2: Evaluate approaches

   Greedy fails here because picking largest coin first may not yield minimum coins (e.g., amount=6, greedy picks 4+1+1=3 coins, but 3+3=2 coins is better). Simple recursion repeats subproblems causing inefficiency. DP stores results to avoid repeated work and finds optimal solution efficiently.

3. Final Answer:

   Dynamic Programming to store and reuse subproblem results -> Option D

4. Quick Check:

   Minimum coins with overlapping subproblems = DP [OK]

Hint: Use DP for minimum coins; greedy can fail with some denominations [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring efficiency of memoization
• Using brute force causing timeouts