Data Structures and Algorithms · Techniques

Divide and conquer

Splitting a problem into independent smaller copies of itself, solving each, then combining.

Also known as: D&C, split and combine.

Start a lesson on Divide and conquer

Learn first

• Divide-and-conquer sorting: Divide-and-conquer sorts, merge sort and quicksort, that beat O(n squared) by splitting the problem.

Leads to

• Dynamic programming: Solving a problem by caching answers to overlapping subproblems instead of recomputing them.

Related topics

• Binary search: Repeatedly halving a sorted range to find a target in logarithmic time.
• Dynamic programming: Solving a problem by caching answers to overlapping subproblems instead of recomputing them.