Divide-and-conquer algorithm: Difference between revisions

Revision as of 06:47, 13 September 2019

Revision as of 15:10, 24 December 2019

Line 38:

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 ''n'', and (b) there is a bounded number ''p'' of subproblemssub-problems of size ~ ''n''/''p'' at each stage, then the cost of the divide-and-conquer algorithm will be O(''n'' log_''p''''n'').

=== Parallelism ===