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?"

Practice

1. Which approach is best when a problem can be broken into overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand overlapping subproblems

   Dynamic Programming works well when subproblems repeat and can be reused.

2. Step 2: Check optimal substructure property

   Dynamic Programming uses optimal solutions of subproblems to build the final solution.

3. Final Answer:

   Dynamic Programming -> Option A

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 subproblems overlap
• Using simple recursion without memoization causing slow code
• Confusing brute force with DP

2. Which of the following TypeScript function signatures correctly implements a recursive Fibonacci function?

easy

A. function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); }

B. function fib(n: number): number { let a = 0; let b = 1; for(let i=2; i<=n; i++) { let c = a + b; a = b; b = c; } return b; }

C. function fib(n: number): number { return n + fib(n-1); }

D. function fib(n: number): number { if(n == 0) return 0; else return fib(n-1) * fib(n-2); }

Solution

1. Step 1: Check base case correctness

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } returns n if n <= 1, which correctly handles fib(0)=0 and fib(1)=1.

2. Step 2: Check recursive calls

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } calls fib(n-1) + fib(n-2), matching Fibonacci definition.

3. Final Answer:

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } -> Option A

4. Quick Check:

   Correct base case and recursive sum = function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } [OK]

Hint: Base case n<=1 and sum of fib(n-1)+fib(n-2) is key [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using multiplication instead of addition
• Incorrect loop instead of recursion

3. What is the output of the following TypeScript code using recursion to calculate factorial?

function factorial(n: number): number {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. 10

B. Error

C. 120

D. 24

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) = 4 * factorial(3), factorial(3) = 3 * factorial(2), factorial(2) = 2 * factorial(1), factorial(1) = 1 * factorial(0), factorial(0) = 1.

2. Step 2: Calculate values bottom-up

   factorial(0) = 1, factorial(1) = 1*1=1, factorial(2) = 2*1=2, factorial(3) = 3*2=6, factorial(4) = 4*6=24.

3. Final Answer:

   24 -> Option D

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial n! = n*(n-1)! with base 0! = 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Missing base case causing stack overflow
• Incorrect multiplication order

4. The following greedy algorithm tries to find the minimum number of coins for a given amount. What is the bug?

function minCoins(coins: number[], amount: number): number {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (let coin of coins) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return count;
}
console.log(minCoins([1, 3, 4], 6));

medium

A. Sorting coins ascending instead of descending

B. Greedy fails for coin sets where local choice isn't optimal

C. Using floor division instead of ceil

D. Not handling zero amount input

Solution

1. Step 1: Understand greedy approach for coin change

   Greedy picks largest coin first, but it may not yield minimum coins for all coin sets.

2. Step 2: Check example with coins [1,3,4] and amount 6

   Greedy picks 4 once, then 1 twice = 3 coins; but optimal is 3+3 = 2 coins.

3. Final Answer:

   Greedy fails for coin sets where local choice isn't optimal -> Option B

4. Quick Check:

   Greedy not always optimal for coin change [OK]

Hint: Greedy fails if local best choice isn't globally best [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring coin sorting order
• Confusing floor and ceil division

5. You want to find the longest increasing subsequence (LIS) in an array. Which approach is best and why?
const arr = [10, 9, 2, 5, 3, 7, 101, 18];

hard

A. Greedy, because picking local max always gives LIS

B. Recursion without memoization, to explore all subsequences

C. Dynamic Programming, to store LIS lengths and build solution efficiently

D. Brute force, checking all subsequences

Solution

1. Step 1: Analyze problem characteristics

   LIS requires checking many subsequences with overlapping subproblems and optimal substructure.

2. Step 2: Choose approach with efficiency

   Dynamic Programming stores LIS lengths for subproblems, avoiding repeated work and improving speed.

3. Final Answer:

   Dynamic Programming, to store LIS lengths and build solution efficiently -> Option C

4. Quick Check:

   LIS best solved by DP due to overlapping subproblems [OK]

Hint: Use DP for LIS to avoid exponential recursion [OK]

Common Mistakes:

• Using greedy which fails for LIS
• Recursion without memoization causing slow code
• Trying brute force which is inefficient