DivideAndConquer

1. Overview

Divide and Conquer is an algorithmic design paradigm that works by recursively breaking down a problem into sub-problems of a similar type until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give solution to the original problem.

• Divide: Break the given problem into subproblems of the same type
• Conquer: Recursively solve these subproblems
• Combine: Appropriately combine the answers

2. Description

2.1 Procedure

2.2 Property

2.2.1 Optimal Substructure

• Any problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblem.
• Ex: Fib(n) = Fib(n-1) + Fib(n-2)

3. Example

3.1 Merge sort

3.2 Quick sort

3.3 Binary search

4. Reference

https://www.geeksforgeeks.org/divide-and-conquer/