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

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

O(2^n) recursion, O(n) dynamic programming, O(n) greedy (when applicable)

Understanding Time Complexity

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

We want to see how the time needed changes with input size for each approach.

Scenario Under Consideration

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

// Recursive Fibonacci
function fibRec(n: number): number {
  if (n <= 1) return n;
  return fibRec(n - 1) + fibRec(n - 2);
}

// Dynamic Programming Fibonacci
function fibDP(n: number): number {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// Greedy-like approach (not suitable here but example)
// For some problems, greedy picks best local choice
// No code here as greedy depends on problem specifics

These functions calculate Fibonacci numbers using recursion and dynamic programming.

Identify Repeating Operations

Look at what repeats in each approach.

• Recursive: Calls itself twice per call, many repeated calculations.
• Dynamic Programming: Uses a loop to build answers once each.
• Greedy: Picks best choice step-by-step, no repeated work (if applicable).
• Dominant operation: Recursive calls vs loop iterations.

How Execution Grows With Input

See how the number of steps grows as input grows.

Input Size (n)	Recursive Calls	DP Loop Iterations
10	~177 calls	10 iterations
20	~21,891 calls	20 iterations
30	~2,692,537 calls	30 iterations

Recursive calls grow very fast, DP grows slowly and linearly.

Final Time Complexity

Time Complexity: O(2^n) for recursion, O(n) for dynamic programming, and O(n) or better for greedy when applicable.

This means recursion can get very slow as input grows, DP is efficient by reusing work, and greedy is fast if the problem fits.

Common Mistake

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

[OK] Correct: Recursion is simple and fine for small inputs or when combined with memoization (DP). It's not always slow if used wisely.

Interview Connect

Understanding these approaches helps you pick the right tool for problems and explain your choices clearly, a key skill in interviews.

Self-Check

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