divide and conquer

A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.

In more detail

Merge sort splits a list in half, sorts both halves and merges them; binary search is the one-branch case that recurses into only one half. The cost follows from a recurrence relation such as T(n) = 2T(n/2) + n. It works best when the pieces do not overlap; when they do, dynamic programming avoids solving them twice.

Related terms

Taught in

References