= Solution
<Divide-and-conquer algorithms> suit problems with largely independent, balanced subproblems and an inexpensive combination step. In <merge sort>, the two halves are independently sorted and merged in linear time. Its <recurrence relation> is $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n)$, giving $\Theta(n\log n)$ <time complexity>.
<Dynamic programming> suits overlapping subproblems with a compact state description. For the <coin change problem>, let $C(v)$ be the minimum number of coins needed to make amount $v$. With positive denominations $D$ containing $1$,
$$
C(0)=0,\qquad C(v)=1+\min_{d\in D,\ d\leq v}C(v-d).
$$
Every optimal nonempty answer has a last coin $d$ and an optimal answer for $v-d$; otherwise replacing the remainder improves it. Filling $C(0),\ldots,C(V)$ takes $O(V|D|)$ <time complexity> and $O(V)$ <space complexity>. Repeated amounts are computed just once. This bound is in the numeric amount $V$, not its binary input length.
A <greedy algorithm> suits problems where one can prove a <greedy-choice property>. For unweighted <interval scheduling>, choose an interval with earliest finishing time, discard overlapping intervals, and repeat. Among optimal schedules, replace the first interval by the earliest-finishing one. The replacement finishes no later, so every later interval remains feasible. Applying the same argument to the remaining intervals proves optimality. After sorting by finish time, a single scan suffices.
These examples separate the relevant structural reasons: independent halves, repeated amount states, and an exchange argument certifying each irreversible choice.
Back to article page
