Divide-and-conquer algorithm

In computer science, divide and conquer, originally a political maxim, designates an algorithm design paradigm.

Uses your system voice; voice and rate in settings.

≈ 2 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, divide and conquer, originally a political maxim, designates an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g., the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), SAT solving, and computing the discrete Fourier transform (FFT). Designing efficient divide-and-conquer algorithms can be difficult.

As in mathematical induction, it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1363143428 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001363143428 · captured 2026-07-08 · ledger · version history

Cite this page as: encyclopegia.org, “Divide-and-conquer algorithm”, snapshot enwiki-001363143428. https://encyclopegia.org/a/divide-and-conquer-algorithm

Sources cited in this revision

8 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.