Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
The Master theorem classifies balanced divide-and-conquer recurrences by comparing f(n) with n^{log_b a}.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
n is problem size; a≥1 and b>1 are dimensionless; T and f use matching cost units
| Symbol | Meaning | Unit |
|---|---|---|
| Number of equal subproblems | dimensionless | |
| Subproblem shrink factor | dimensionless | |
| Nonrecursive work per call | computational cost | |
| Exponent log_b(a) | dimensionless |
T(n)=aT(n/b)+\Theta(n^d(\log n)^k)Let p=log_b(a). Polynomially smaller f(n) gives Θ(n^p); equal order gives the standard Θ(n^p log n) case; polynomially larger f(n) gives Θ(f(n)) only with regularity a f(n/b)≤c f(n), c<1. Extensions treat logarithmic factors. The recurrence must match the theorem’s form; it does not solve arbitrary recurrences.
Let p=log_b(a). Polynomially smaller f(n) gives Θ(n^p); equal order gives the standard Θ(n^p log n) case; polynomially larger f(n) gives Θ(f(n)) only with regularity a f(n/b)≤c f(n), c<1. Extensions treat logarithmic factors. The recurrence must match the theorem’s form; it does not solve arbitrary recurrences.
The Master theorem classifies balanced divide-and-conquer recurrences by comparing f(n) with n^{log_b a}.
kritischer Exponent
Compare f(n) with n^p and check the applicable case conditions.
Use the example for Master theorem for recurrences to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
The Master theorem classifies balanced divide-and-conquer recurrences by comparing f(n) with n^{log_b a}.
The relation applies only under its stated assumptions.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: Let p=log_b(a). Polynomially smaller f(n) gives Θ(n^p); equal order gives the standard Θ(n^p log n) case; polynomially larger f(n) gives Θ(f(n)) only with regularity a f(n/b)≤c f(n), c<1. Extensions treat.
Formula cluster
The Master theorem classifies balanced divide-and-conquer recurrences by comparing f(n) with n^{log_b a}.
Merge sort has T(n)=2T(n/2)+Θ(n). Here p=log22=1 and f(n)=Θ(n), hence T(n)=Θ(n log n). A recursion tree has Θ(n) work on each of Θ(log n) levels.
Estimate runtime recurrences for merge sort and balanced divide-and-conquer.
Here is how to work through a typical Master theorem for recurrences (T(n) = aT(n/b) + f(n)) task step by step:
Task
Use the example for Master theorem for recurrences to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
The Master theorem classifies balanced divide-and-conquer recurrences by comparing f(n) with n^{log_b a}.
The relation applies only under its stated assumptions.
For T(n)=aT(n/b)+f(n), recursive subproblems create about a^j calls at level j, with size n/b^j. Leaf work is proportional to n^{log_b a}. Set p=log_b(a), then compare f(n) with n^p. Their relative growth determines which part of the recursion tree dominates runtime. The theorem classifies a specified recurrence; it is not a shortcut for every recursive program. Write the recurrence and verify the case assumptions before applying it. The quantities a and b are constants, while n denotes input size rather than runtime. Finite suitable base cases normally do not change the asymptotic order.
In the standard form, f(n)=Θ(n^p), where p=log_b(a), means each recursion-tree level contributes the same order. There are Θ(log n) levels, so T(n)=Θ(n^p log n). Merge sort has a=2, b=2 and f(n)=Θ(n), giving p=1 and Θ(n log n). Additional logarithmic factors need the extended theorem’s case statement. The theorem classifies a specified recurrence; it is not a shortcut for every recursive program. Write the recurrence and verify the case assumptions before applying it. The conclusion assumes a recurrence with a constant reduction factor and suitable asymptotic functions. Solving n/b^j≈1 gives j≈log_b(n), the recursion-tree depth.
When f(n) grows polynomially faster than n^p, the third case gives Θ(f(n)) only if work shrinks geometrically into recursive children. A common regularity condition is a f(n/b)≤c f(n), with constant c<1. Without it, the top-level work may not dominate lower levels. Growth comparison alone is insufficient. The theorem classifies a specified recurrence; it is not a shortcut for every recursive program. Write the recurrence and verify the case assumptions before applying it. Checking regularity is especially important when the nonrecursive work dominates. Check recursive subproblem work, rather than comparing only the top-level term.
Its assumptions include a fixed number of equal-size subproblems, a consistent shrink factor and suitable nonrecursive work. Unequal splits, significant floors, multiple branch sizes or irregular f(n) may need substitution, recursion trees or another theorem. Model the algorithm first; forcing it into Master form can produce a plausible but unsupported bound. The theorem classifies a specified recurrence; it is not a shortcut for every recursive program. Write the recurrence and verify the case assumptions before applying it. Choosing a case without checking the recurrence form may give an incorrect result despite plausible Θ notation. Akra–Bazzi handles broader split patterns, but still requires an explicit recurrence.
Each merge-sort level processes all n elements across its subproblems, so work per level is Θ(n). Repeated halving reaches size one after Θ(log2n) levels. Their product is Θ(n log n). The base leaves total Θ(n), which does not change the order. This tree calculation independently checks the theorem’s result. The theorem classifies a specified recurrence; it is not a shortcut for every recursive program. Write the recurrence and verify the case assumptions before applying it. The level-by-level calculation provides a second derivation and exposes the logarithmic number of levels. Other algorithms may have different total work on different recursion-tree levels.
Quanta exam set
Curated exam set for "Master theorem for recurrences":
Question (front)
Which formula describes Master theorem for recurrences?
Answer in your set
Question (front)
How do you rearrange Master theorem for recurrences for kritischer Exponent?
Answer in your set
Question (front)
Which common mistake happens with Master theorem for recurrences?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for T(n) = aT(n/b) + f(n): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential