# Divide-and-Conquer (DnC)

Recursively, many algorithms try to call themselves multiple times for solving tightly relevant sub-problems.

The DnC paradigm takes the following steps:

1. DIVIDE original problem into sub-problems
2. CONQUER each sub-problem recursively
3. (\*) COMBINE solutions for sub-problem into one for the original problem

   ***Note**: some problems don't have combination phase; for instance, BinarySearch will search for specified element in either the left (n /2) or the right (n /2) of an array and return that element if found.*

## Table of Contents

* [Multiplication](https://cs-notes.gitbook.io/algorithm-notes/outline/overview/multiplication) - chapter about integer multiplication, matrix multiplication and polynomial multiplication.
* [Master Method](https://cs-notes.gitbook.io/algorithm-notes/outline/overview/master-method) - a generalized form of mathematical interpretation is given for DnC problems.
* [DnC Strategy](https://cs-notes.gitbook.io/algorithm-notes/outline/overview/dnc-strategy) - several different strategies for various problems will be covered.