3. Decrease and Conquer

Decrease and conquer algorithms take the following approach:

1. Decrease or reduce the problem instance to smaller instance of the same problem.

2. Conquer the problem by solving smaller instance of the problem.

3. Extend solution of smaller instance to obtain solution to original problem .

Basic intuition of the decrease-and-conquer technique is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance. This approach is also known as incremental or inductive approach.

Fig. 3.1 Decrease and Conquer

Decrease and Conquer algorithms contrasts with the Divide and Conquer approach in the scope of the problem reduction.

Fig. 3.2 Decrease and Conquer vs. Divide and Conquer

Decrease and Conquer	Divide and Conquer
Problem is reduced to a smaller instances in a chain like manner, piecing off one element at a time	Problem is reduced to two or more smaller instances in a tree like manner
Decrease by a constant amout Think subtraction n = n - constant at each step	Decrease by a constant factor Think division n = n / constant at each step
Example: Insertion, Selection Sort	Example: Binary Search, Merge Sort