## Principle

Unlike dynamic programming, sub-problem results are only useful for the outcome of the parent problem.

The divide and conquer algorithm breaks down into three stages:

- Divide: the problem is broken down into b sub-problems of size n/b. These sub-problems are of the same nature as their parent. We are in the presence of identical subproblems. When b = 2, we are talking about dichotomy.
- Rule: sub-problems are solved recursively.
- Combine: sub-problem solutions are recommended to rebuild the solution to the initial problem.

## Example

In order to better understand the construction of the algorithm, we will take the example of rapid exponentiation. The principle of this algorithm is to calculate x^{n}.

In order to use the divide and conquer method, we need to find a mathematical program to rewrite our problem into equivalent sub-problems. Since this is a recursive method, do not forget to include a final state. We are therefore in the presence of the following mathematical program:

Traduction of french words: Initial/If n is even/Otherwise

The algorithm is as follows:

double power(double x, int n) {if(n==0) return 1;else{if(n%2==0) return power(x*x, n/2);elsereturn x*power(x*x, (n-1)/2);end ifend if}

Its complexity is in 0(log n) – size of the complete binary tree with n vertices.