Divide-and-conquer algorithm: Difference between revisions

Revision as of 12:13, 23 December 2023

Revision as of 12:15, 23 December 2023

Line 34:

=== 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>n/p</math> at each stage, then the cost of the divide-and-conquer algorithm will be <math>O(n\log_{p}n)</math>.