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

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

O(2^n) for recursion, O(n) for DP, O(k * (amount / min_coin)) for 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 changes as the problem size grows.

Scenario Under Consideration

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

// Recursive Fibonacci (simple recursion)
int fib_recursive(int n) {
  if (n <= 1) return n;
  return fib_recursive(n-1) + fib_recursive(n-2);
}

// Dynamic Programming Fibonacci (bottom-up)
int fib_dp(int n) {
  int dp[n+1];
  dp[0] = 0; dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

// Greedy example (coin change with unlimited coins)
int coin_change_greedy(int coins[], int size, int amount) {
  int count = 0;
  for (int i = size - 1; i >= 0; i--) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return count;
}

These snippets show recursion, dynamic programming, and greedy approaches for common problems.

Identify Repeating Operations

Look at loops and repeated calls that affect speed.

• Recursive Fibonacci: Calls itself twice per call, many repeated calculations.
• DP Fibonacci: One loop from 2 to n, calculates each value once.
• Greedy coin change: Outer loop over coin types, inner loop subtracts coins until amount is small.
• Dominant operation: Recursive calls in recursion, single loop in DP, nested loops in greedy.

How Execution Grows With Input

See how operations increase as input size grows.

Input Size (n)	Recursive Fib Calls	DP Fib Steps	Greedy Coin Steps
10	~177 calls	10 steps	Depends on amount and coins
20	~21,891 calls	20 steps	Depends on amount and coins
30	~2,692,537 calls	30 steps	Depends on amount and coins

Recursive calls grow very fast, DP grows slowly and linearly, greedy depends on coin values and amount.

Final Time Complexity

Time Complexity: O(2^n) for recursion, O(n) for DP, O(k * (amount / min_coin)) for greedy

Recursion can be very slow, DP is efficient by reusing results, greedy depends on problem specifics.

Common Mistake

[X] Wrong: "Greedy always gives the best answer quickly."

[OK] Correct: Greedy works only if the problem has a special structure; otherwise, it can give wrong answers.

Interview Connect

Understanding these approaches helps you pick the right tool for different problems and explain your choices clearly.

Self-Check

"What if we add memoization to the recursive Fibonacci? How would the time complexity change?"