Editing Divide-and-conquer algorithm (section)

=== Algorithm efficiency ===
The divide-and-conquer paradigm often helps in the discovery of efficient algorithms.  It was the key, for example, to [[Karatsuba algorithm|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 complexity|asymptotic cost]] of the solution. For example, if (a) the [[Recursion (computer science)|base cases]] have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size <math>n</math>, and (b) there is a bounded number <math>p</math> of sub-problems of size ~ <math>\frac{n}{p}</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.

For other types of divide-and-conquer approaches, running times can also be generalized. For example, when a) the work of splitting the problem and combining the partial solutions take <math>cn</math> time, where <math>n</math> is the input size and <math>c</math> is some constant; b) when <math>n < 2</math>, the algorithm takes time upper-bounded by <math>c</math>, and c) there are <math>q</math> subproblems where each subproblem has size ~ <math>\frac{n}{2}</math>. Then, the running times are as follows:

* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.
* if the number of subproblems is exactly one, then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book |last1=Kleinberg |first1=Jon |last2=Tardos |first2=Eva |title=Algorithm Design |date=March 16, 2005 |publisher=[[Pearson Education]] |isbn=9780321295354 |pages=214-220 |edition=1 |url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 |access-date=26 January 2025}}</ref>

If, instead, the work of splitting the problem and combining the partial solutions take <math>cn^2</math> time, and there are 2 subproblems where each has size <math>\frac{n}{2}</math>, then the running time of the divide-and-conquer algorithm is bounded by <math>O(n^2)</math>.<ref name="kleinberg&Tardos"/>