🐬 Paradigms

A paradigm is a general problem-solving strategy that applies across many unrelated problems — not a single named algorithm (Algorithms), not a specific reusable trick (Techniques), not a way of organising data (Data Structures). “Greedy” and “divide and conquer” are paradigms; “Dijkstra’s algorithm” and “two pointers” are not. This page is a map of which paradigm to reach for and why it’s correct — each row links to the note doing the actual work, not a re-explanation here.

Choosing a paradigm

Paradigm	Needs, to be correct	Typical complexity shape	Classic example
Brute force / complete search	nothing — exhaustive by construction	$O(\text{search space})$	try every subset, $n\le 20$
Greedy	an exchange argument or a matroid structure	usually $O(n\log n)$, one pass after sorting	interval scheduling
Divide and conquer	the problem splits into independent subproblems that recombine cheaply	$T(n)=aT(n/b)+f(n)$, master theorem	merge sort, FFT
Dynamic programming	optimal substructure + overlapping subproblems	$O(\text{states}\times \text{transition})$	knapsack, LIS
Backtracking / branch and bound	a pruning bound that’s cheap to compute and often tight	exponential worst case, pruned in practice	N-queens, TSP exact
Randomized (Monte Carlo / Las Vegas)	a probability-of-success or expected-time argument	depends on the algorithm; often a $\log$ or ​ factor over the deterministic bound	randomized quickselect, Karger’s min cut
Local search / metaheuristics	no correctness guarantee at all — a heuristic	anytime: runs until you stop it	simulated annealing
Approximation algorithms	a provable ratio to the true optimum, for an NP-hard problem	polynomial, ratio stated explicitly	2-approx vertex cover
Reduction-based modeling	the reduction preserves answers in both directions	cost of the target algorithm (max flow, 2-SAT, LP)	scheduling as min cut
Game-tree search / minimax	the game is finite, perfect-information, zero-sum (or handled explicitly if not)	$O(b^d)$, pruned by alpha-beta	chess engines, Nim-adjacent game solving

By paradigm

Brute force / complete search

Enumerate the entire search space, or a space small enough that enumeration is the algorithm. The paradigm that needs no proof of correctness beyond “every case was checked” — the only question is whether the space is small enough, and whether a smarter representation (bitmask, meet in the middle) shrinks it. See Backtracking and Meet in the Middle.

Greedy

Make the locally-best choice at each step and never revisit it. Correctness is never “obviously true” — it needs an exchange argument (swapping any two choices doesn’t improve the answer) or, for the strongest version, a proof that the problem’s feasible choices form a matroid. See Greedy and Exchange Arguments and Matroids.

Divide and conquer

Split a problem into independent (or nearly independent) subproblems, solve each recursively, recombine. The master theorem classifies the three regimes by whether the recombination cost dominates, balances, or is dominated by the recursive cost. See Divide and Conquer.

Dynamic programming

Store answers to subproblems and reuse them. Needs both optimal substructure (the optimal solution is built from optimal solutions to subproblems) and overlapping subproblems (the same subproblem recurs, otherwise plain recursion already suffices). The entire DP chapter is this paradigm applied to dozens of state shapes. See DP Foundations.

Backtracking and branch and bound

Explore the search space via recursion, abandoning (pruning) a branch the moment it provably cannot beat the best answer found so far. The paradigm’s entire value is in the pruning bound: cheap to compute, and tight enough to cut most of the tree in practice even though the worst case stays exponential. See Backtracking and Informed Search (A*/IDA*, heuristic-guided pruning).

Randomized algorithms

Use randomness either to bound the expected running time with a guaranteed-correct output (Las Vegas: randomized quickselect) or to accept a bounded probability of a wrong answer in exchange for speed (Monte Carlo: Miller–Rabin). See Randomized Algorithms.

Local search and metaheuristics

Start from some solution and repeatedly move to a neighbouring one that looks better, with no proof of optimality — used when the problem is too hard for anything exact and a good-enough answer under a time limit is the actual goal. See Randomized Search (simulated annealing, hill climbing).

Approximation algorithms

For an NP-hard problem, give up exactness on purpose and prove a bound on how far from optimal the answer can be (a ratio, additive or multiplicative). The paradigm is defined by the proof of the ratio, not by any one technique for finding the approximate solution. See Approximation Algorithms.

Reduction-based modeling

Recast the actual problem as an instance of a different problem with a known efficient algorithm — max flow/min cut, 2-SAT, bipartite matching, linear programming — and solve that instead. The paradigm’s correctness is entirely in the reduction: showing the translation preserves feasibility and optimality in both directions. See Flow Modeling and 2-SAT.

Game-tree search / minimax

For a finite, perfect-information, zero-sum two-player game, recursively assume both players play optimally and propagate values up the game tree; alpha-beta pruning cuts branches that can’t change the result. See Game DP and Minimax.

When paradigms collide

Looks like…	But actually needs…	The distinguishing question
Greedy	DP	Does a locally-best choice ever need to be revisited once more information arrives? If yes, it’s DP.
Backtracking	DP	Do the same subproblems recur across different branches? If yes, memoize it — that’s DP wearing backtracking’s clothes.
Divide and conquer	DP	Do the subproblems overlap? D&C assumes independence; if they overlap, it’s DP (or [[05-divide-and-conquer/01-divide-and-conquer
Exact algorithm	Approximation	Is the problem actually NP-hard for the input sizes given? If $n$ is too large for exact and the problem is hard, stop looking for an exact greedy/DP and reach for a proven ratio instead.
Backtracking	Randomized local search	Is the search space too large to prune down to a tractable size even with a good bound? That’s the signal to switch from guaranteed-correct exhaustive search to a heuristic.

See also Complexity and Analysis for the constraint-to-complexity table that often decides which paradigm is even feasible before correctness is considered, and Before Contest for the same decision guide compressed into a one-screen lookup.