# Master theorem (analysis of algorithms)
The master theorem is a result in the analysis of algorithms that gives the asymptotic running time of many divide-and-conquer recurrences of the form \( T(n) = aT(n/b) + f(n) \), where \( a \geq 1 \) subproblems of size \( n/b \) (with \( b > 1 \)) are solved recursively and \( f(n) \) is the non-recursive work of splitting and combining, provided the recurrence meets the conditions of one of its cases.[12](https://www.cs.yale.edu/homes/aspnes/pinewiki/SolvingRecurrences.html) It was first published by Jon Louis Bentley, Dorothea Haken, and James B. Saxe in 1980 and was popularized as the "master method" by the textbook *[Introduction to Algorithms](https://www.edgepedia.org/introduction-to-algorithms)* by Cormen, Leiserson, Rivest, and Stein (CLRS).[1](https://ocw.cs.pub.ro/ppcarte/lib/exe/fetch.php?media=aa%3Amaster.pdf) • [2](https://web.engr.oregonstate.edu/~huanlian/algorithms_course/1-datastructures/master.html)
| Key fact | Detail |
|---|---|
| Recurrence form | \( T(n) = aT(n/b) + f(n) \), with \( a \geq 1 \) (branching factor), \( b > 1 \) (division factor), and \( f(n) \) the divide-plus-combine work[2](https://web.engr.oregonstate.edu/~huanlian/algorithms_course/1-datastructures/master.html) |
| Decision quantity | Compare \( f(n) \) with \( n^{\log_b a} \), the work contributed by the leaves of the recursion tree[3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html) |
| Case 1 (leaves dominate) | If \( f(n) = O(n^{\log_b a - \epsilon}) \) for some \( \epsilon > 0 \), then \( T(n) = \Theta(n^{\log_b a}) \)[3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html) |
| Case 2 (balanced) | If \( f(n) = \Theta(n^{\log_b a}) \), then \( T(n) = \Theta(f(n)\log n) \); the extended form with \( f(n) = \Theta(n^{\log_b a}\log^k n) \) gives \( \Theta(n^{\log_b a}\log^{k+1} n) \)[3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html) • [4](https://math.umd.edu/~immortal/CMSC351/notes/mastertheorem.pdf) |
| Case 3 (root dominates) | If \( f(n) = \Omega(n^{\log_b a + \epsilon}) \) and the regularity condition \( af(n/b) \leq cf(n) \) holds for some \( c < 1 \), then \( T(n) = \Theta(f(n)) \)[3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html) |
| Classic results | Binary search: \( T(n) = T(n/2) + O(1) \in O(\log n) \); mergesort: \( T(n) = 2T(n/2) + O(n) \in O(n\log n) \)[5](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-7.6.html) |
| Main generalization | The Akra–Bazzi method (1998) handles recurrences with unequal subproblem sizes, a superset of the recurrences the master method covers[1](https://ocw.cs.pub.ro/ppcarte/lib/exe/fetch.php?media=aa%3Amaster.pdf) |
## The recurrence and its parameters
A divide-and-conquer algorithm splits an input of size \( n \) into \( b \) roughly equal, non-overlapping pieces, recursively solves \( a \) of them, and spends \( f(n) \) work outside the recursive calls to divide the input and combine the partial solutions. The running time therefore satisfies \( T(n) = aT(n/b) + f(n) \). The parameter \( a \) is the branching factor of the recursion tree and must satisfy \( a \geq 1 \); \( b \) is the factor by which the problem shrinks and must satisfy \( b > 1 \), since otherwise the recursion would never terminate. Both are constants. In mergesort, \( a = b = 2 \) and \( f(n) = n \); in binary search, \( a = 1 \), \( b = 2 \), and \( f(n) = 1 \), because only one of the two halves is searched.[2](https://web.engr.oregonstate.edu/~huanlian/algorithms_course/1-datastructures/master.html) • [6](https://courses.cs.washington.edu/courses/cse417/25au/readings/divide_and_conquer.html)
Floors and ceilings, which arise when \( n \) is not divisible by \( b \), have a negligible impact on the asymptotics and are usually dropped.[3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html)
## The recursion-tree argument
The theorem is derived by summing the work per level of the recursion tree. Level 0 does \( f(n) \) work; level \( h \) has \( a^h \) nodes, each of size \( n/b^h \), for a total of \( a^h f(n/b^h) \). The tree has height \( \log_b n \), and the last level contains \( a^{\log_b n} = n^{\log_b a} \) leaves, each contributing constant work, so the leaves together do \( \Theta(n^{\log_b a}) \) work.[2](https://web.engr.oregonstate.edu/~huanlian/algorithms_course/1-datastructures/master.html) • [3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html)
The three cases ask which side of the tree dominates. As one moves down the tree, the number of subproblems grows exponentially while the work per subproblem shrinks exponentially; the critical exponent \( \log_b a \) is exactly the point where these two rates balance. If the per-level work geometrically increases toward the leaves (case 1), the leaves dominate and \( T(n) = \Theta(n^{\log_b a}) \).[13](https://courses.csail.mit.edu/6.006/spring11/rec/rec08.pdf) If it stays within a constant factor (case 2), all \( \log_b n \) levels contribute comparably and a logarithmic factor is added. If it grows (case 3), the per-level work decreases geometrically toward the leaves, so the root dominates the total work, subject to the regularity condition \( af(n/b) \leq cf(n) \) for some \( c < 1 \) and all sufficiently large \( n \), which ensures this geometric decrease.[3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html) • [4](https://math.umd.edu/~immortal/CMSC351/notes/mastertheorem.pdf) • [14](https://www.cs.cornell.edu/courses/cs3110/2010sp/Lectures/lec20.html)
The \( \epsilon \) in cases 1 and 3 requires a polynomial gap: \( f(n) = O(n^{\log_b a - \epsilon}) \) means \( f \) is smaller than \( n^{\log_b a} \) by a factor of at least \( n^{\epsilon} \). For example \( n^{1.9} = O(n^{2-\epsilon}) \) with \( \epsilon = 0.01 \), but \( n^2/\log n \) is not \( O(n^{2-\epsilon}) \) for any \( \epsilon > 0 \), so a bare case-1 application fails for such an \( f \).[3](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html)
## Worked examples
**Binary search.** \( T(n) = T(n/2) + O(1) \): here \( a = 1 \), \( b = 2 \), and \( k = 0 \) in the polynomial-work form \( f(n) = O(n^k) \). Since \( a = b^k \), case 2 applies and \( T(n) \in O(n^k \log n) = O(\log n) \).[5](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-7.6.html)
**Mergesort.** \( T(n) = 2T(n/2) + O(n) \): \( a = 2 \), \( b = 2 \), \( k = 1 \), again \( a = b^k \), so \( T(n) \in O(n \log n) \).[5](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-7.6.html)
**More subproblems than the work can pay for.** \( T(n) = 3T(n/2) + O(n) \): \( a = 3 > b^k = 2 \), so the recursive work dominates and \( T(n) \in O(n^{\log_2 3}) \approx O(n^{1.6}) \).[5](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-7.6.html)
**Expensive combining.** \( T(n) = 3T(n/2) + O(n^2) \): \( a = 3 < b^k = 4 \), so the extra work dominates and \( T(n) \in O(n^2) \).[5](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-7.6.html)
**Logarithmic factors in the work.** For \( T(n) = 9T(n/3) + n^2 \lg n \), \( \log_b a = \log_3 9 = 2 \) matches the exponent of \( f(n) \), so the extended case 2 with \( k = 1 \) gives \( T(n) = \Theta(n^2 \lg^2 n) \).[4](https://math.umd.edu/~immortal/CMSC351/notes/mastertheorem.pdf)
## Scope and limitations
The theorem applies only to recurrences in standard form with constant \( a \) and \( b \). It does not apply to \( T(n) = 2T(n/4) + 3T(n/2) + n \), which has the wrong form, and technically not to \( k \)-way mergesort, \( T(n) = kT(n/k) + n\log k \), when \( k \) is a variable rather than a constant, although that recurrence would otherwise fit case 2.[4](https://math.umd.edu/~immortal/CMSC351/notes/mastertheorem.pdf) • [2](https://web.engr.oregonstate.edu/~huanlian/algorithms_course/1-datastructures/master.html) The theorem also cannot be applied from partial information alone: knowing only \( f(n) = O(n^2) \) for \( T(n) = 2T(n/4) + f(n) \) does not let case 1 fire, because \( \log_b a = 0.5 \) is not greater than 2.[4](https://math.umd.edu/~immortal/CMSC351/notes/mastertheorem.pdf)
The presentation has changed between editions of CLRS. The recurrence \( T(n) = 2T(n/2) + n\log n \) is not covered by the master method as stated in edition 3, but edition 4 extends case 2 to work functions that match \( n^{\log_b a} \) up to a logarithmic factor, and this recurrence is covered there.[7](https://github.com/pl3onasm/CLRS/blob/main/algorithms/theory/recurrences/master-method.md)
## Generalizations
In 1998, [Mohamad Akra](https://www.edgepedia.org/mohamad-akra) and Louay Bazzi developed a more general method for recurrence relations that covers unequal subproblem sizes, of the form \( T(x) = \sum_i a_i T(b_i x + h_i(x)) + g(x) \); it addresses a superset of the recurrences covered by the master method.[1](https://ocw.cs.pub.ro/ppcarte/lib/exe/fetch.php?media=aa%3Amaster.pdf) For recurrences with more than one recursive term of different sizes, such as \( T(n) = \tfrac14 T(n/16) + \tfrac13 T(3n/5) + 4T(n/100) + 10T(n/300) + n^2 \), master-type theorems for multiple-size recurrences have been established.[8](https://arxiv.org/abs/cs/0101011)
Discreteness introduces its own effects. Michael Drmota and Wojciech Szpankowski proved a master theorem for discrete divide-and-conquer recurrences, in which the floor function introduces oscillations not captured by the traditional theorem or by Akra and Bazzi, who studied the continuous version.[9](https://epubs.siam.org/doi/10.1137/1.9781611973082.28) Olivier Garet gave in 2019 a master theorem for discrete recurrences \( X_n = a_n + \sum_j b_j X_{\lfloor p_j n \rfloor} \) that requires no regularity or monotonicity assumption on the driving sequence \( (a_n) \), allowing even random \( (a_n) \) arising from randomized algorithms.[10](https://arxiv.org/abs/1902.10600) Carl D. Offner, a mathematician at the [University of Massachusetts Boston](https://www.edgepedia.org/university-of-massachusetts-boston), published in 2025 what he describes as a general, best-possible form of the master theorem for divide-and-conquer recurrences, tracing the lineage from the original Bentley–Haken–Saxe theorem through Akra and Bazzi and Leighton.[11](https://arxiv.org/abs/2507.16064)
## References
1. [Jon Louis Bentley, Dorothea Haken, and James B. Saxe (1980), "A General Method for Solving Divide-and-Conquer Recurrences", ACM SIGACT News 12.3, pp. 36–44; as cited in "The Master Method" lecture notes, Politehnica University of Bucharest OCW](https://ocw.cs.pub.ro/ppcarte/lib/exe/fetch.php?media=aa%3Amaster.pdf)
2. [1.9 Master Theorem and Summary of Common Recurrences, Huan Li, Oregon State University](https://web.engr.oregonstate.edu/~huanlian/algorithms_course/1-datastructures/master.html)
3. [CSC236 Summer 2025, Lecture 06: Recurrences 2, University of Toronto](https://www.cs.toronto.edu/~shaharry/csc236-summer-2025/lectures/l6-s.html)
4. [CMSC 351: The Master Theorem, lecture notes, University of Maryland](https://math.umd.edu/~immortal/CMSC351/notes/mastertheorem.pdf)
5. [DSABook – Deriving the Master theorem, Chalmers University of Technology](https://chalmersgu-data-structure-courses.github.io/dsabook/html/section-7.6.html)
6. [CSE417 – Divide and Conquer, University of Washington](https://courses.cs.washington.edu/courses/cse417/25au/readings/divide_and_conquer.html)
7. [The master method (CLRS recurrences notes), pl3onasm/CLRS on GitHub](https://github.com/pl3onasm/CLRS/blob/main/algorithms/theory/recurrences/master-method.md)
8. [Multiple-Size Divide-and-Conquer Recurrences, arXiv:cs/0101011](https://arxiv.org/abs/cs/0101011)
9. [Michael Drmota and Wojciech Szpankowski, "A Master Theorem for Discrete Divide and Conquer Recurrences", SODA 2011, pp. 342–361](https://epubs.siam.org/doi/10.1137/1.9781611973082.28)
10. [Olivier Garet (2019), "A simple Master Theorem for Discrete Divide and Conquer Recurrences", arXiv:1902.10600](https://arxiv.org/abs/1902.10600)
11. [Carl D. Offner (2025), "A Best Possible General Form of the Master Theorem for Divide-and-Conquer Recurrences", arXiv:2507.16064](https://arxiv.org/abs/2507.16064)
12. [SolvingRecurrences](https://www.cs.yale.edu/homes/aspnes/pinewiki/SolvingRecurrences.html)
13. [courses.csail.mit.edu](https://courses.csail.mit.edu/6.006/spring11/rec/rec08.pdf)
14. [Lecture 19: Recursion Trees and the Master Method](https://www.cs.cornell.edu/courses/cs3110/2010sp/Lectures/lec20.html)
---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Algorithms overview*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license