When D&C Beats Alternatives

D&C works well when: $1.$ Subproblems are independent: Unlike DP where subproblems overlap.

$2.$ Combining is efficient: If combining is $O(n^2)$, D&C may not help.

$3.$ Problem structure is recursive: Naturally splits into similar subproblems.

D&C vs DP:

• D&C: Subproblems don't overlap. Solve each once.
• DP: Subproblems overlap. Memoize to avoid recomputation.

D&C vs Greedy:

• D&C: Consider all subproblems.
• Greedy: Make one choice, never backtrack.

Red flags for D&C: If the combination step dominates (e.g., must consider all pairs), D&C may not reduce complexity.