Loading field map
Every algorithm is a response to a single, pressing question: how can computation be structured to solve a problem within the resources available? The answer is never obvious. A naive program that tries all possibilities may run for centuries on even modest inputs. Over the past seventy years, computer scientists have distilled a small set of reusable strategies—design paradigms—that transform this question into a manageable engineering choice. Each paradigm makes a different bet about how to decompose work, explore possibilities, or accept imperfection. The history of these paradigms is not a tidy succession of replacements; it is a story of accumulating trade-offs, where each new approach preserved something from its predecessors while sacrificing something else to handle problems the earlier methods could not.
The first two paradigms, Divide and Conquer (1948–Present) and Dynamic Programming (1956–Present), both attack a problem by breaking it into smaller pieces. Their difference lies in what they assume about those pieces.
Divide and Conquer, formalized in the late 1940s alongside early stored-program computers, splits a problem into independent subproblems, solves each recursively, and combines the results. The independence assumption is its strength and its limit. Merge sort, for example, divides an array into halves that have no interaction; the sorted halves can be merged in linear time. The paradigm works brilliantly when subproblems do not overlap, but it offers no help when the same subproblem recurs across different branches of the recursion tree.
Dynamic Programming, introduced by Richard Bellman in his 1956 book Dynamic Programming, directly addresses that limitation. Bellman recognized that many optimization problems—shortest paths, sequence alignment, resource allocation—revisit the same subproblems repeatedly. Instead of recomputing them, Dynamic Programming stores their solutions in a table and reuses them. The key intellectual move is the identification of overlapping subproblems and an optimal substructure: the optimal solution to the whole problem must contain optimal solutions to its subproblems. Where Divide and Conquer assumes independence, Dynamic Programming exploits dependence. The cost is a more complex analysis of state spaces and a higher memory footprint, but the payoff is a dramatic reduction in time for problems like the knapsack or the edit distance between strings.
By 1960, researchers had begun to confront problems that resisted clean decomposition: constraint satisfaction puzzles, combinatorial optimization, and decision problems with no obvious substructure. Two closely related paradigms emerged to organize exhaustive search.
Backtracking (1960–Present) incrementally builds candidate solutions and abandons a partial candidate as soon as it becomes clear that it cannot lead to a valid complete solution. The classic example is the eight queens puzzle: place queens one row at a time, and when a placement conflicts with earlier queens, undo it and try the next column. Backtracking is a depth-first search of the solution space, pruned by constraints. It requires no special problem structure beyond the ability to test partial solutions, which makes it broadly applicable but also potentially exponential in the worst case.
Branch and Bound (1960–Present) extends Backtracking from feasibility to optimization. Where Backtracking only checks whether a partial solution violates constraints, Branch and Bound also computes a bound on the best possible solution that could be completed from that partial state. If the bound is worse than the current best known solution, the branch is pruned. This addition transforms the search: the algorithm can now prove that entire regions of the search space cannot contain an optimal solution, even if they are feasible. Branch and Bound thus preserves Backtracking's incremental construction and pruning logic but adds a quantitative optimization criterion. The two paradigms have coexisted ever since, with Backtracking preferred for constraint satisfaction and Branch and Bound for problems like the traveling salesman or integer programming where an objective function must be minimized or maximized.
In 1971, Jack Edmonds published a paper on matroids and the greedy algorithm that gave a precise mathematical answer to an old question: when can a series of locally optimal choices produce a globally optimal solution? The Greedy Algorithms paradigm (1971–Present) makes the boldest assumption of any design strategy: that the problem's structure is such that a myopic decision at each step never needs to be undone.
Edmonds showed that the greedy algorithm works exactly when the feasible solutions form a matroid—a combinatorial structure satisfying an exchange property. For the minimum spanning tree problem, Kruskal's algorithm repeatedly picks the cheapest edge that does not create a cycle; the matroid property guarantees that this local rule yields a global minimum. The paradigm is extraordinarily efficient, often running in near-linear time, but its applicability is narrow. Most optimization problems do not have matroid structure, and when they do not, a greedy choice can lead arbitrarily far from the optimum. Greedy Algorithms thus stand in sharp contrast to Dynamic Programming, which can handle overlapping subproblems without requiring the exchange property, and to Branch and Bound, which explores many alternatives rather than committing to one.
The early 1970s brought a sobering realization: many natural problems, including the traveling salesman, graph coloring, and integer programming, are NP-hard. No polynomial-time algorithm is known for them, and a polynomial-time algorithm for any one would revolutionize the field. Designers faced a choice: accept exponential worst-case time, or relax the requirement for an exact, deterministic solution. Two paradigms emerged from this pressure, each relaxing a different guarantee.
Approximation Algorithms (1973–Present) sacrifice optimality for speed. Instead of demanding the exact best solution, an approximation algorithm guarantees a solution within a proven factor of the optimum. The field was launched by a 1974 paper by David S. Johnson, Approximation Algorithms for Combinatorial Problems, which gave the first systematic treatment of worst-case performance ratios. For example, the greedy algorithm for the set cover problem can be shown to produce a solution no worse than (ln n) times the optimal. Approximation Algorithms preserve the deterministic, worst-case analysis style of earlier paradigms but accept that the answer may be imperfect. They are the natural extension of Greedy's trade-off logic: if local choice cannot guarantee optimality, it can at least guarantee a bounded error.
Randomized Algorithms (1976–Present) sacrifice determinism rather than optimality. By making random choices during execution, a randomized algorithm can often achieve polynomial expected time for problems where deterministic algorithms seem to require exponential time. The paradigm gained visibility with the Miller–Rabin primality test, which uses randomness to decide whether a number is prime with a controllable probability of error. Randomized Algorithms coexist with Approximation Algorithms as parallel responses to intractability, but they relax a different dimension: they give up certainty about the algorithm's behavior, not about the quality of the output. In practice, the two are often combined—randomized approximation algorithms offer both speed and bounded error—and they remain active research areas.
Today, no single paradigm dominates. Each occupies a distinct niche defined by its assumptions and guarantees. Divide and Conquer remains the default for problems with independent subproblems, from sorting to fast Fourier transforms. Dynamic Programming is the workhorse for optimization over sequences and graphs with overlapping structure. Backtracking and Branch and Bound are the tools of choice for constraint programming and exact optimization in operations research. Greedy Algorithms provide the fastest solutions when matroid or similar structure holds. Approximation Algorithms are the standard response to NP-hard optimization problems where a proven bound is required. Randomized Algorithms offer simplicity and speed for problems like load balancing, hashing, and primality testing.
The paradigms agree on one fundamental principle: the structure of a problem should dictate the choice of strategy. They disagree on what counts as a solution—exact or approximate, deterministic or probabilistic—and on how much problem-specific analysis is worthwhile. A designer today rarely picks a single paradigm in isolation. Hybrid algorithms are common: a randomized approximation algorithm may use Dynamic Programming as a subroutine, or a Branch and Bound search may be guided by a greedy heuristic. The history of the paradigms is not a story of obsolescence but of accumulating options, each with a clear set of trade-offs that a thoughtful designer can exploit.
The seven design paradigms—Divide and Conquer, Dynamic Programming, Backtracking, Branch and Bound, Greedy Algorithms, Approximation Algorithms, and Randomized Algorithms—form a conceptual toolkit for managing computational complexity. They emerged in a rough historical sequence, each responding to a limitation of its predecessors: independence gave way to overlap, feasibility search gave way to optimization search, local choice was formalized, and exactness was relaxed in two different directions. The result is a living set of strategies that continue to be refined, combined, and taught as the foundation of algorithm design.