The divide-and-conquer strategy solves a problem by:
Breaking it into subproblems that are themselves smaller instances of the same type of
problem
Recursively solving these subproblems
Appropriately combining their answers
The real work is done piecemeal, in three different places: in the partitioning of problems
into subproblems; at the very tail end of the recursion, when the subproblems are so small
that they are solved outright; and in the gluing together of partial answers. These are held
together and coordinated by the algorithm’s core recursive structure. The ultimate example
of such an algorithm is “Binary Search”.
The running time of a divide-and-conquer algorithm can be analysed using the master theorem.
