Greedy vs DP How to Know Which to Apply in DSA Typescript - Complexity Comparison

Time Complexity: Greedy vs DP How to Know Which to Apply

O(n)

Understanding Time Complexity

When deciding between Greedy and Dynamic Programming (DP), understanding how their time costs grow helps us choose the right method.

We want to know which approach runs faster as the problem size grows.

Scenario Under Consideration

Analyze the time complexity of these two simplified approaches.

// Greedy approach example
function greedySolution(items: number[]): number {
  let total = 0;
  for (const item of items) {
    if (item > 0) total += item;
  }
  return total;
}

// DP approach example
function dpSolution(items: number[]): number {
  const dp = new Array(items.length + 1).fill(0);
  for (let i = 1; i <= items.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 1] + items[i - 1]);
  }
  return dp[items.length];
}
    

The greedy function sums positive items quickly. The DP function considers combinations to find the best sum.

Identify Repeating Operations

Look at the loops and repeated steps in each approach.

• Greedy primary operation: One loop over all items.
• Greedy loop count: Runs once for each item (n times).
• DP primary operation: One loop filling the dp array.
• DP loop count: Also runs once for each item (n times), but does extra work inside.

How Execution Grows With Input

Both methods loop through the input once, but DP does more work per step.

Input Size (n)	Greedy Approx. Operations	DP Approx. Operations
10	~10 simple checks	~10 calculations and comparisons
100	~100 simple checks	~100 calculations and comparisons
1000	~1000 simple checks	~1000 calculations and comparisons

Pattern observation: Both grow linearly, but DP does more work per item.

Final Time Complexity

Time Complexity: O(n) for both Greedy and DP in this example.

This means both take time proportional to the number of items, but DP usually has more steps per item.

Common Mistake

[X] Wrong: "Greedy is always faster and better than DP."

[OK] Correct: Greedy is faster but only works when local choices lead to a global best. DP handles complex cases but may be slower.

Interview Connect

Knowing when to pick Greedy or DP shows you understand problem patterns and efficiency, a key skill interviewers look for.

Self-Check

"What if the DP solution used nested loops to compare all pairs? How would the time complexity change?"