Divide-and-conquer algorithm
Algorithm efficiency

The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example, to Karatsuba 's fast multiplication method, the quicksort and mergesort algorithms, the Strassen algorithm for matrix multiplication, and fast Fourier transforms.

In all these examples, the D&C approach led to an improvement in the asymptotic cost of the solution. For example, if (a) the base cases have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size n {\displaystyle n}, and (b) there is a bounded number p {\displaystyle p} of sub-problems of size ~ n / p {\displaystyle n/p} at each stage, then the cost of the divide-and-conquer algorithm will be O (n log p n) {\displaystyle O(n\log _{p}n)}.
language:response_language[Latin]