Divide-and-conquer algorithm
Recursively breaks problems into simpler sub-problems and combines solutions.
Divide-and-conquer is an algorithm design paradigm in computer science that recursively breaks a problem into two or more sub-problems of the same or related type until they become simple enough to solve directly, then combines the sub-solutions to solve the original problem. Originally a political maxim, it is the basis of efficient algorithms for sorting, multiplying large numbers, finding the closest pair of points, syntactic analysis, SAT solving, and computing the discrete Fourier transform.
The paradigm’s core idea is to decompose a given problem into similar but simpler subproblems, solve those in turn, and compose their solutions. Problems of sufficient simplicity are solved directly. For instance, to sort a list, one can split it into two roughly equal halves, sort each half, and then interleave the results—this is the merge sort algorithm. Designing efficient divide-and-conquer algorithms can be difficult, often requiring generalization of the problem to enable a recursive solution, much like mathematical induction. Correctness is typically proved by induction, and computational cost is determined by solving recurrence relations.
The name is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as binary search. These can be implemented more efficiently, especially if they use tail recursion, which can be converted into simple loops. However, under this broad definition, nearly every recursive or loop-based algorithm would qualify, so some authors reserve the term for problems generating two or more subproblems, using “decrease and conquer” for the single-subproblem class. In optimization, if the search space is reduced by a constant factor at each step, the overall algorithm has the same asymptotic complexity as the pruning step—this is known as prune and search.
Early historical examples are primarily decrease-and-conquer. Binary search dates back to Babylonia in 200 BC, and the Euclidean algorithm for greatest common divisors is several centuries old. A notable early multi-subproblem divide-and-conquer algorithm was Gauss’s 1805 description of the fast Fourier transform, though it was not quantitatively analyzed and remained obscure until rediscovered over a century later. The first specifically computer-oriented two-subproblem algorithm was merge sort, invented by John von Neumann in 1945. Another milestone w
- field
- Computer science
- known_for
- Algorithm design paradigm; basis of quicksort, merge sort, Karatsuba algorithm, FFT
- related_concepts
- Decrease and conquer, prune and search, mathematical induction, recurrence relations
Lore & Background
The divide-and-conquer technique is often used to find optimal solutions by decomposing a given problem into two or more similar but simpler subproblems, solving them in turn, and composing their solutions. Problems of sufficient simplicity are solved directly. For example, to sort a list of natural numbers, one splits it into two lists of about half the size, sorts each, and interleaves the results—this is the merge sort algorithm. Some authors restrict the name to algorithms that generate two or more subproblems, proposing 'decrease and conquer' for single-subproblem cases like binary search.
Reader's Guide
The divide-and-conquer paradigm is significant because it enables the discovery of efficient algorithms for conceptually difficult problems. It was key to Karatsuba's fast multiplication method, quicksort, mergesort, Strassen's matrix multiplication, and fast Fourier transforms. Designing efficient divide-and-conquer algorithms can be difficult, often requiring generalization of the problem as in mathematical induction. Correctness is usually proved by mathematical induction, and computational cost is often determined by solving recurrence relations. The paradigm also includes 'prune and search' for optimization, where the search space is reduced by a constant factor at each step.
Did You Know?
- The name 'divide and conquer' originally was a political maxim before being adopted in computer science.
Frequently Asked Questions
Who is Divide-and-conquer algorithm?
Divide-and-conquer is a foundational algorithm design paradigm in computer science that recursively splits a problem into smaller sub-problems of the same or related type until they are simple enough to solve directly, then stitches those partial answers back together. It is not a single algorithm but a reusable strategy that many well-known algorithms follow.
What are Divide-and-conquer algorithm's powers and role?
It is the underlying strategy behind quicksort, merge sort, Karatsuba's multiplication method, the fast Fourier transform, closest-pair-of-points, syntactic parsing, and SAT solving. In the broader landscape it sits alongside related paradigms such as decrease-and-conquer and prune-and-search.
How does Divide-and-conquer algorithm's story end?
The recursion bottoms out at sub-problems small enough to be resolved in constant time, after which the algorithm merges every partial result back up the recursion tree to deliver the final answer for the original input.
Why is Divide-and-conquer algorithm important?
It gives computer scientists a general, provably efficient framework for taming otherwise unwieldy problems, and its correctness and running-time bounds are established through recurrence relations and mathematical induction. Without it, many of the fastest known solutions in sorting, number theory, and signal processing would not exist.
What is Divide-and-conquer algorithm's origin?
Before it became a cornerstone of algorithm design, the phrase was originally a political maxim about ruling by splitting opponents into factions. It was later formalized in computer science as a recursive strategy for breaking problems into independent sub-problems.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record