# Difference between sequential and parallel divide and conquer

In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy

In divide and conquer, we solve a problem recursively, applying three steps at each level of recursion:

Divide the problem into a number of subproblems that are smaller instances of the same problem

Conquer the subproblems by solving them recursively. If the subproblems sizes are small enough, however, just solve the problems in a straight forward manner.

Combine the solutions into the solution of the original problem.

This algorithmic strategy is assumed on sequential machines and is a non-parallel divide and conquer strategy.

How is parallel divide and conquer different from the above? Which step among divide, conquer, combine will be different?

My assumption is that the dividing step will not change and combine step will not change, but only the conquer step changes and the change will be that each subproblem will be solved in parallel. Is it true?

• Parallel divide and conquer is implemented using what is called fork-join parallelism. – Dan D. Feb 11 '19 at 13:01