Divide & Conquer

The Divide and Conquer paradigm splits a massive computational problem into subproblems of the same type, solves them recursively, and combines their solutions to achieve superior complexity.

The 3-Step Triad

1. Divide

Break original input $S$ into $k$ non-overlapping subproblems.

2. Conquer

Recursively solve each subproblem until base case size.

3. Combine

Merge sub-solutions into the final global answer.

Quick Summary

Divide & Conquer powers Merge Sort, Karatsuba multiplication, and fast matrix operations.
Next, we explore Greedy Algorithms.