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
- recurrence relation — An equation that defines an algorithm's cost on input size n in terms of its cost on smaller inputs, such as T(n) = 2T(n/2) + n.
- merge sort — A divide-and-conquer sort that splits the list in half, sorts each half recursively and then merges the two sorted halves.
- binary search — Finding a target in sorted data by comparing it with the middle item and throwing away the half where it cannot be.
- master theorem — A ready-made rule that solves recurrences of the form T(n) = aT(n/b) + f(n) by comparing f(n) with n raised to log base b of a.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers