Case 1: leaves dominate
f(n) = O(n^(c−ε))
For some ε > 0, the additive work grows polynomially slower. Result: Θ(n^c).
Master Theorem Recurrence Complexity Calculator
Enter the recurrence parameters
T(n) = aT(n/b) + Θ(n^k(log n)^p)
A whole number, at least 1.
A finite number greater than 1.
For n, use 1; for 1, use 0.
Use 0 when there is no log factor.
Examples:
Private by design: the recurrence parameters are analyzed on this device. They are not uploaded, stored, or added to the page URL.
Advertisement
How the Master Theorem cases work
For T(n)=aT(n/b)+f(n), calculate c=log_b(a) and compare f(n) with n^c. The comparison describes whether work is concentrated near the recursion-tree leaves, balanced across levels, or concentrated near the root.
Case 2: levels balance
f(n) = Θ(n^c)
In the classic boundary case, each level contributes the same order. Result: Θ(n^c log n).
Case 3: root dominates
f(n) = Ω(n^(c+ε))
If the regularity condition also holds, the additive work wins. Result: Θ(f(n)).
When f(n)=Θ(n^k(log n)^p) and k=c, the logarithm exponent refines the boundary: p>−1 gives Θ(n^c(log n)^(p+1)), p=−1 gives Θ(n^c log log n), and p<−1 gives Θ(n^c).
Master Theorem examples
| Algorithm or pattern | Recurrence | Comparison | Result |
|---|---|---|---|
| Merge sort | 2T(n/2) + Θ(n) | k = log₂2 = 1 | Θ(n log n) |
| Binary search | T(n/2) + Θ(1) | k = log₂1 = 0 | Θ(log n) |
| Karatsuba multiplication | 3T(n/2) + Θ(n) | 1 < log₂3 | Θ(n^(log₂3)) |
| Strassen matrix multiplication | 7T(n/2) + Θ(n²) | 2 < log₂7 | Θ(n^(log₂7)) |
| Root-dominated work | 2T(n/2) + Θ(n²) | 2 > log₂2 | Θ(n²) |
Assumptions and limits
This calculator assumes a is a fixed positive integer, b>1 is fixed, subproblems have equal size n/b, and the nonrecursive work has the asymptotic form Θ(n^k(log n)^p). Floors and ceilings in the subproblem size do not normally change the resulting asymptotic class under the theorem’s standard conditions.
Equality between k and log_b(a) is tested with a relative floating-point tolerance of 10⁻¹⁰. Inputs that differ only below this numerical tolerance are treated as the boundary case. Displayed decimal exponents are rounded to 10 significant digits; the symbolic log_b(a) form remains the exact statement.
The classic three-case theorem does not cover every recurrence. Unequal subproblem sizes such as T(n/3)+T(2n/3), coefficients that depend on n, and additive terms outside the supported polynomial-logarithmic family may require substitution, a recursion tree, or the Akra–Bazzi method. The calculated class describes asymptotic growth, not exact running time or constant factors.
Calculation note: results follow the standard Master Theorem comparison and its common logarithmic boundary extension for f(n)=Θ(n^k(log n)^p). Last reviewed: .
Master Theorem calculator FAQ
What recurrence form does the Master Theorem use?
The standard form is T(n)=aT(n/b)+f(n), where a≥1 is the number of recursive subproblems, b>1 is the shrink factor, and f(n) is the work outside the recursive calls.
What does n^(log_b a) represent?
It represents the aggregate contribution associated with the recursion-tree leaves. Comparing it with f(n) reveals which part of the tree determines the total asymptotic work.
Which case applies when f(n) equals n^(log_b a)?
For f(n)=Θ(n^(log_b a)), classic Case 2 applies. The balanced work across the recursion levels adds a factor of log n, producing Θ(n^(log_b a) log n).
Can f(n) include a logarithmic factor?
Yes. Set p to represent (log n)^p. The calculator includes the extended boundary results when k=log_b(a), including negative logarithm exponents.
What is the Case 3 regularity condition?
Case 3 requires a f(n/b) ≤ c f(n) for some constant c<1 and sufficiently large n. In the supported polynomial-logarithmic family, k>log_b(a) makes the limiting ratio a/b^k<1, so the condition holds asymptotically.
Can the Master Theorem solve every recurrence?
No. It is designed for fixed-size, equal divide-and-conquer subproblems. Unequal splits, changing coefficients, and other additive functions can fall outside its scope.
Does the base of log n change the complexity?
No. Changing a logarithm’s base multiplies it by a positive constant, which does not change its Big-Theta class. The base matters in log_b(a) because that value is an exponent.
Are my recurrence inputs uploaded or stored?
No. The recurrence is validated and analyzed locally in your browser. Copy and download actions also happen on your device.