Divide and rule
Unlike the dynamic programming, the results of the sub-problems are only useful for the result of the parent problem.
In order to better understand the construction of the algorithm, we will take the example of fast exponentiation. The principle of this algorithm is to calculate xnot.
In order to use the divide and conquer method, we need to find a mathematical program that allows us to rewrite our problem into equivalent subproblems. Since this is a recursive method, don't forget to include a final state. We are therefore in the presence of the following mathematical program:
The algorithm is as follows:
Its complexity is 0 (log n) - size of the complete binary tree at not tops.