Starlight Tools

Master Theorem Recurrence Complexity Calculator

Find the asymptotic complexity of a divide-and-conquer recurrence in the form T(n) = aT(n/b) + Θ(n^k(log n)^p). The calculator identifies the applicable classic or logarithmic Master Theorem case and shows why.

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.

Complexity result

The merge sort example is analyzed below.

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 1: leaves dominate

f(n) = O(n^(c−ε))

For some ε > 0, the additive work grows polynomially slower. Result: Θ(n^c).

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 patternRecurrenceComparisonResult
Merge sort2T(n/2) + Θ(n)k = log₂2 = 1Θ(n log n)
Binary searchT(n/2) + Θ(1)k = log₂1 = 0Θ(log n)
Karatsuba multiplication3T(n/2) + Θ(n)1 < log₂3Θ(n^(log₂3))
Strassen matrix multiplication7T(n/2) + Θ(n²)2 < log₂7Θ(n^(log₂7))
Root-dominated work2T(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.

Explore more tools