Karatsuba in 1960 that could multiply two n-digit numbers in O ( n log 2 ⁡ 3 ). Īnother notable example is the algorithm invented by Anatolii A. Another ancient decrease-and-conquer algorithm is the Euclidean algorithm to compute the greatest common divisor of two numbers by reducing the numbers to smaller and smaller equivalent subproblems, which dates to several centuries BC.Īn early example of a divide-and-conquer algorithm with multiple subproblems is Gauss's 1805 description of what is now called the Cooley–Tukey fast Fourier transform (FFT) algorithm, although he did not analyze its operation count quantitatively, and FFTs did not become widespread until they were rediscovered over a century later.Īn early two-subproblem D&C algorithm that was specifically developed for computers and properly analyzed is the merge sort algorithm, invented by John von Neumann in 1945. While a clear description of the algorithm on computers appeared in 1946 in an article by John Mauchly, the idea of using a sorted list of items to facilitate searching dates back at least as far as Babylonia in 200 BC. Īn important application of divide and conquer is in optimization, where if the search space is reduced ('pruned') by a constant factor at each step, the overall algorithm has the same asymptotic complexity as the pruning step, with the constant depending on the pruning factor (by summing the geometric series) this is known as prune and search.Įarly examples of these algorithms are primarily decreased and conquer – the original problem is successively broken down into single subproblems, and indeed can be solved iteratively.īinary search, a decrease-and-conquer algorithm where the subproblems are of roughly half the original size, has a long history. The name decrease and conquer has been proposed instead for the single-subproblem class. Therefore, some authors consider that the name 'divide and conquer' should be used only when each problem may generate two or more subproblems. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a 'divide-and-conquer algorithm'. These algorithms can be implemented more efficiently than general divide-and-conquer algorithms in particular, if they use tail recursion, they can be converted into simple loops. The name 'divide and conquer' is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the binary search algorithm for finding a record in a sorted list (or its analogue in numerical computing, the bisection algorithm for root finding). This approach is known as the merge sort algorithm. Problems of sufficient simplicity are solved directly.įor example, to sort a given list of n natural numbers, split it into two lists of about n/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem.

The divide-and-conquer paradigm is often used to find an optimal solution of a problem. Upper half: splitting into sublists mid: a one-element list is trivially sorted lower half: composing sorted sublists. 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.ĭivide and conquer Divide-and-conquer approach to sort the list (38, 27, 43, 3, 9, 82, 10) in increasing order. As in mathematical induction, it is often necessary to generalize the problem to make it amenable to a recursive solution. ĭesigning efficient divide-and-conquer algorithms can be difficult. 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), and computing the discrete Fourier transform ( FFT). The solutions to the sub-problems are then combined to give a solution to the original problem. 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. In computer science, divide and conquer is an algorithm design paradigm.

Algorithms which recursively solve subproblems

Divide and conquer algorithm