DP vs Recursion vs Greedy Choosing the Right Tool in DSA Java - 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 your code runs.

We want to see how the time needed grows as the problem size grows for each approach.

Scenario Under Consideration

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

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

// DP Fibonacci with memoization
int fibDP(int n, int[] memo) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fibDP(n-1, memo) + fibDP(n-2, memo);
  return memo[n];
}

// Greedy-like approach (not suitable here, but example)
int fibGreedy(int n) {
  if (n <= 1) return n;
  int a = 0, b = 1;
  for (int i = 2; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
  }
  return b;
}
    

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

Identify Repeating Operations

Look at how many times the main calculations repeat.

• Recursive: Calls itself twice per step, many repeated calculations.
• DP: Each number calculated once and stored, avoids repeats.
• Greedy-like: Simple loop from 2 to n, no repeats.

How Execution Grows With Input

As n grows, see how operations increase.

Input Size (n)	Recursive Calls	DP Calls	Greedy Iterations
10	~177	11	9
100	Huge (exponential)	101	99
1000	Very huge (exponential)	1001	999

Recursive grows very fast, DP and greedy grow linearly with n.

Final Time Complexity

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

Recursive repeats work many times, DP and greedy do each step once, so they are faster as n grows.

Common Mistake

[X] Wrong: "Recursion is always slow and greedy is always fast."

[OK] Correct: Some greedy solutions don't work correctly, and recursion with memoization (DP) can be very efficient.

Interview Connect

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

Self-Check

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

Practice

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

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion

D. Brute Force

Solution

1. Step 1: Understand problem properties

   Overlapping subproblems means 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 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
• Confusing optimal substructure with greedy choice property

2. Which of the following Java method signatures correctly represents a recursive function to compute factorial?

easy

A. public static int factorial(int n) { if (n == 1) return 0; else return n + factorial(n - 1); }

B. public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); }

C. public static int factorial(int n) { for (int i = 1; i <= n; i++) return i; }

D. public static int factorial(int n) { while (n > 0) n = n - 1; return n; }

Solution

1. Step 1: Check base case correctness

   Factorial base case is 0! = 1, so if (n == 0) return 1 is correct.

2. Step 2: Check recursive call and calculation

   Factorial(n) = n * factorial(n-1) is correct recursive formula.

3. Final Answer:

   public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } -> Option B

4. Quick Check:

   Correct base case and recursive multiplication = public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } [OK]

Hint: Factorial recursion multiplies n by factorial(n-1) with base n=0 [OK]

Common Mistakes:

• Wrong base case (e.g., returning 0 instead of 1)
• Using loops instead of recursion
• Returning addition instead of multiplication

3. What will be the output of the following Java code snippet?

public class Test {
  public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.println(fib(4));
  }
}

medium

A. 3

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2). fib(3) = fib(2) + fib(1), fib(2) = fib(1) + fib(0).

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1, so fib(2)=1+0=1, fib(3)=1+1=2, fib(4)=2+1=3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Fibonacci(4) = 3 by adding previous two Fibonacci numbers [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Adding wrong recursive results
• Assuming fib(4) = 5 (fibonacci(5))

4. Identify the error in this greedy algorithm code snippet for coin change problem:

public static int minCoins(int[] coins, int amount) {
  int count = 0;
  for (int coin : coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return count;
}

medium

A. Missing base case for amount = 0

B. Should use recursion instead of loops

C. Coins array must be sorted in descending order

D. Count variable should be reset inside the loop

Solution

1. Step 1: Understand greedy coin change logic

   Greedy picks largest coin first to minimize count. Coins must be sorted descending for this to work.

2. Step 2: Check code for sorting

   Code does not sort coins, so if coins are unsorted, greedy picks smaller coins first, leading to wrong answer.

3. Final Answer:

   Coins array must be sorted in descending order -> Option C

4. Quick Check:

   Greedy coin change needs descending sorted coins [OK]

Hint: Sort coins descending for greedy coin change to work correctly [OK]

Common Mistakes:

• Not sorting coins before greedy selection
• Using recursion unnecessarily
• Resetting count inside loop causing wrong count

5. You want to find the minimum number of jumps to reach the end of an array where each element represents max jump length at that position. Which approach is best and why?

int[] arr = {2,3,1,1,4};

hard

A. Use Dynamic Programming to store minimum jumps for each index

B. Use simple recursion to try all jump combinations

C. Use Brute Force to check every path

D. Use Greedy approach to jump to the farthest reachable index

Solution

1. Step 1: Analyze problem nature

   Minimum jumps problem can be solved efficiently by greedy because at each step, jumping to the farthest reachable index reduces total jumps.

2. Step 2: Compare approaches

   Recursion or DP works but are slower. Greedy gives optimal solution in linear time for this problem.

3. Final Answer:

   Use Greedy approach to jump to the farthest reachable index -> Option D

4. Quick Check:

   Minimum jumps = Greedy farthest jump [OK]

Hint: Jump farthest reachable index greedily for minimum jumps [OK]

Common Mistakes:

• Using recursion causing timeouts
• Overcomplicating with DP when greedy suffices
• Ignoring problem constraints for greedy validity