Divide-and-conquer algorithm

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, divide and conquer is an <a href="/facts/Algorithm_design_paradigm/KaykS57Y">algorithm design paradigm</a>. A divide-and-conquer <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursively</a> 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 <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting</a> (e.g., <a href="/facts/Quicksort/1BeqhLAH">quicksort</a>, <a href="/facts/Merge_sort/A5jLYfzS">merge sort</a>), <a href="/facts/Multiplication_algorithm/68xf6EdK">multiplying large numbers</a> (e.g., the <a href="/facts/Karatsuba_algorithm/YFk3dnqX">Karatsuba algorithm</a>), finding the <a href="/facts/Closest_pair_of_points_problem/54Aw1kRV">closest pair of points</a>, <a href="/facts/Syntactic_analysis/nRKB01S3">syntactic analysis</a> (e.g., <a href="/facts/Top-down_parser/VVqphs5y">top-down parsers</a>), and computing the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a> (<a href="/facts/Fast_Fourier_transform/caT7UUCh">FFT</a>).
Designing efficient divide-and-conquer algorithms can be difficult. As in <a href="/facts/Mathematical_induction/KxAPqNrH">mathematical induction</a>, it is often necessary to generalize the problem to make it amenable to a <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursive</a> solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving <a href="/facts/Recurrence_relation/JolXC71M">recurrence relations</a>.

Divide-and-conquer algorithm open-in-new

Divide-and-conquer algorithm