Notes by Lex Toumbourou

Decrease and Conquer is a class of Algorithm where a Problem is solved by reducing to a smaller, similar problem, which we solve recursively.

Examples:

• Binary Search: to find a specific value in a sorted array, the algorithm repeatedly halved the part of the list that contains the item, decreasing the problem size at each step until an item is found or the list is empty.
• Insertion Sort: builds the final sorted array one item at a time. It takes an element from the list and places it in the correct place relative to the sorted part of the list.

Not to be confused with Divide-and-Conquer, which divides a problem into two or smaller, independent problems, solving each recursively and combining the solution.