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.
- 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
Elsewhere in the Algorithms And Data Structures universe
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