Master theorem

The Master theorem gives asymptotic bounds for recurrences of the form T(n)=aT(n/b)+f(n), comparing the recursive work with the nonrecursive work.

Recurrence tree method: A method for solving recurrences by summing work across levels of a recursive computation. It exposes the same balance between per-level work and recursion depth that the theorem summarizes.
Divide-and-conquer algorithm: An algorithmic strategy that divides a problem into smaller subproblems, solves them recursively, and combines their results. The theorem models the recursive structure used by this algorithmic strategy.
Merge sort: A comparison-sorting algorithm that recursively sorts two halves and merges them. Its recurrence T(n)=2T(n/2)+Θ(n) falls in the theorem's balanced-work case.
Master theorem for divide-and-conquer recurrences: A generalized form of the Master theorem that handles broader recursive subproblem patterns. This name is sometimes used for extensions that address cases the standard theorem does not cover.
Akra–Bazzi method: A method for asymptotically solving broad classes of divide-and-conquer recurrences, including unequal subproblem sizes. It extends the theorem beyond equal-sized recursive subproblems.
Recurrence relation: An equation defining a sequence or function through values at smaller inputs. The theorem takes a particular recurrence form as its input.
Binary search: A search algorithm that repeatedly halves a sorted search interval. Its recurrence has one half-sized recursive call and constant additional work.
Unequal-subproblem recurrence: A recurrence in which recursive calls have subproblems of different size proportions. The standard theorem assumes every recursive call has the same size reduction factor.
Substitution method: A proof technique that verifies recurrence bounds by induction after proposing a solution. It can prove bounds suggested by the theorem, including bounds in its regularity-sensitive case.
Big O notation: A notation expressing an asymptotic upper bound on a function's growth. The theorem's conclusions are commonly stated as Big O bounds.

Linked from 3 pages

Analysis of algorithmsRelated: It quickly bounds many recursive algorithms by comparing work across recursion levels.