Why Greedy Works and When It Fails in DSA Typescript - Performance Analysis

Time Complexity: Why Greedy Works and When It Fails

O(n + m)

Understanding Time Complexity

We want to understand how fast greedy algorithms run and why their speed depends on the problem.

When does greedy give a quick solution, and when does it take longer or fail?

Scenario Under Consideration

Analyze the time complexity of this simple greedy approach to the coin change problem.

function greedyCoinChange(coins: number[], amount: number): number {
  let count = 0;
  for (let i = coins.length - 1; i >= 0; i--) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return count;
}
    

This code tries to use the largest coin first repeatedly until the amount is covered or no coins left.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: The inner while loop subtracting coins from amount.
• How many times: Up to amount divided by the smallest coin value.

How Execution Grows With Input

As the amount grows, the number of subtractions grows roughly proportional to amount.

Input Size (amount)	Approx. Operations
10	About 10 subtractions
100	About 100 subtractions
1000	About 1000 subtractions

Pattern observation: The work grows roughly linearly with the amount size.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows with the number of coin types (n) plus the amount (m), because the outer loop is O(n) and total inner iterations are O(m).

Common Mistake

[X] Wrong: "Greedy always finds the best answer quickly for any problem."

[OK] Correct: Greedy works fast but can fail to find the best answer if the problem needs looking ahead or combining choices differently.

Interview Connect

Understanding when greedy works helps you pick the right tool and explain your choices clearly in interviews.

Self-Check

"What if the coin denominations were not sorted or included tricky values? How would that affect the time complexity and correctness?"