Master Theorem Calculator
Solve the divide-and-conquer recurrence T(n) = a·T(n/b) + f(n) instantly. Enter a, b, and f(n) = np·logkn, and the calculator determines which of the three Master Theorem cases applies and returns the asymptotic complexity.
Recursion dominates → Θ(nlogba)
Both matter → Θ(nc logk+1 n)
f(n) dominates → Θ(f(n))
Compare a to bp, not a to p
The Master Theorem is often misremembered as "compare logba with p", which is correct but hides the intuition. What you are really comparing is the branching factor a with the per-level work shrinkage factor bp. If the recursion multiplies faster than the work per call shrinks (a > bp), the leaves dominate. If it shrinks faster (a < bp), the root dominates. When they match (a = bp), every level contributes equally and you get an extra log factor.
The recursion tree is the proof
Level i of the recursion tree has ai nodes, each processing a subproblem of size n/bi, so each contributes (n/bi)p = np/bip. Total work at level i is ai · np/bip = np · (a/bp)i. Summing over i gives a geometric series whose behaviour is entirely determined by the ratio a/bp. This is why the Master Theorem works — it is not a magic formula but the closed form of a geometric sum.
Case 3 has a regularity condition
Case 3 requires a regularity condition: a·f(n/b) ≤ c·f(n) for some constant c < 1 and all sufficiently large n. For f(n) = np, this holds automatically whenever p > logba. The condition rules out pathological f(n) that oscillate or fail to shrink when applied recursively. In practice, for polynomial f(n) the condition is always satisfied and you can apply Case 3 without worry.
When the Master Theorem doesn't apply
The Master Theorem fails for recurrences where the subproblems have different sizes (like T(n) = T(n/3) + T(2n/3) + n), where a is not constant, where f(n) is not polynomially bounded (like f(n) = 2n), or where the gap between p and logba is not polynomial (like f(n) = n log n vs n). For those, use the Akra–Bazzi method or the substitution method. This calculator handles the standard polynomial-times-log form, which covers the overwhelming majority of textbook recurrences.
How to Use This Calculator
Enter the four parameters of your divide-and-conquer recurrence and the calculator applies the Master Theorem to find the asymptotic complexity.
1. Enter a and b
a is the number of subproblems (must be a positive integer). b is the divisor on the input size (must be > 1). For T(n) = 2T(n/2) + n, a = 2 and b = 2.
2. Enter p and k for f(n)
Express the non-recursive part as f(n) = np · logk n. For f(n) = n, p = 1, k = 0. For f(n) = n² log n, p = 2, k = 1. For f(n) = 1, p = 0, k = 0.
3. Read the case and result
The result card shows which of the three Master Theorem cases applies (root heavy, balanced, or leaf heavy) and the resulting Θ() complexity.
4. Use the preset examples
Click a preset to load a classic recurrence: merge sort, binary search, Strassen's algorithm, Karatsuba, and others. Useful as a quick sanity check for the tool itself.
5. Check the recursion tree
The tree diagram shows the branching factor a and the depth logbn. When the leaves dominate you see the tree widening; when the root dominates you see the work concentrating at the top.
6. Verify with the comparison chart
The first chart overlays np and nlogba on a log-log plot. Whichever curve is on top tells you which term dominates — and therefore which case applies.
What This Tool Offers
Built around the Master Theorem for divide-and-conquer recurrences — the standard tool for analysing any algorithm that recursively splits its input.
Instant case detection
Automatically identifies Case 1, 2, or 3 from the comparison of logba with p, with a numerical tolerance that handles fractional exponents cleanly.
Full f(n) form
Handles f(n) = np · logk n for any real p and any non-negative integer k, including the extended Case 2 with logarithmic factors.
Recursion tree diagram
A visual of the branching and depth of the recursion, showing why the root, the leaves, or every level contributes the dominant cost.
Side-by-side comparison chart
Plots f(n) and nlogba on the same log-log axes so you can see exactly which one grows faster.
Preset recurrences
Merge sort, binary search, Strassen, Karatsuba, and other textbook algorithms load instantly with a single click.
Reference tables
Common recurrences and their solutions, the three cases side by side, and a variable reference with the formal conditions.
Reference Tables
Common recurrences and their solutions, plus a compact reference to the three Master Theorem cases.
| Algorithm / Recurrence | a | b | f(n) | logba | Case | Result |
|---|---|---|---|---|---|---|
| Merge sort | 2 | 2 | n | 1.000 | 2 | Θ(n log n) |
| Binary search | 1 | 2 | 1 | 0.000 | 2 | Θ(log n) |
| Strassen (matrix mult.) | 7 | 2 | n² | 2.807 | 1 | Θ(n2.807) |
| Karatsuba (integer mult.) | 3 | 2 | n | 1.585 | 1 | Θ(n1.585) |
| Standard matrix mult. | 8 | 2 | n² | 3.000 | 1 | Θ(n³) |
| Linear recursion (find max) | 1 | 2 | n | 0.000 | 3 | Θ(n) |
| Recursive power | 1 | 2 | 1 | 0.000 | 2 | Θ(log n) |
| Closest pair (brute halving) | 2 | 2 | n log n | 1.000 | 2 | Θ(n log² n) |
| Case | Condition | Dominant level | Result |
|---|---|---|---|
| Case 1 | p < logba | Leaves | Θ(nlogba) |
| Case 2 (k = 0) | p = logba | Every level equally | Θ(nlogba · log n) |
| Case 2 (k > 0) | p = logba | Every level equally | Θ(nlogba · logk+1 n) |
| Case 3 | p > logba | Root | Θ(np · logk n) |
What Does the Master Theorem Measure?
The Master Theorem gives the asymptotic solution to a divide-and-conquer recurrence of the form T(n) = a · T(n/b) + f(n), where a ≥ 1 is the number of recursive subproblems, b > 1 is the factor by which the input size shrinks, and f(n) is the non-recursive cost of splitting the problem and combining the results. It is the single most useful tool in algorithm analysis, because almost every classic algorithm — sorting, searching, matrix multiplication, fast Fourier transform, closest pair — has a recurrence of this exact shape.
The Master Theorem
Let c = logba. Then the recurrence T(n) = a·T(n/b) + f(n) has the following solution:
Case 2: if f(n) = Θ(nc · logk n), then T(n) = Θ(nc · logk+1 n)
Case 3: if f(n) = Ω(nc+ε) for some ε > 0, and a·f(n/b) ≤ c'·f(n) for some c' < 1, then T(n) = Θ(f(n))
When f(n) has the form np · logk n (which covers almost every practical case), the conditions simplify dramatically:
p = logba → Case 2: T(n) = Θ(np · logk+1 n)
p > logba → Case 3: T(n) = Θ(np · logk n)
This is exactly what the calculator implements. The only comparison that matters is p vs. logba.
The Recursion Tree Proof
The Master Theorem is not magic — it falls out of a simple geometric series. Level i of the recursion tree has ai nodes, and each node processes a subproblem of size n/bi. If the cost at a node of size m is mp, then the cost at level i is:
The ratio a/bp is the per-level growth factor. If it is less than 1, the level costs form a decreasing geometric series and the total is dominated by level 0 — the root. If it equals 1, every level costs the same and there are logbn levels, so the total is np · logbn. If it is greater than 1, the series increases and the total is dominated by the last level — the leaves.
Comparing a/bp with 1 is the same as comparing logba with p, because a = blogba. This is the equivalence the calculator checks.
Master Theorem Variables
| Symbol | Meaning | Typical values |
|---|---|---|
| a | Number of recursive subproblems | 1, 2, 3, 7, 8 |
| b | Input reduction factor (n/b per subproblem) | 2, 3, 4, 10 |
| p | Exponent of n in f(n) = np · logk n | 0, 1, 2, 3 |
| k | Log factor exponent in f(n) | 0 (usually), 1, 2 |
| c = logba | Critical exponent — the tiebreaker | 0, 1, 1.585, 2.807, 3 |
| f(n) | Non-recursive cost of split + combine | 1, n, n², n log n |
Worked Examples
a = 2, b = 2, p = 1, k = 0
log₂(2) = 1 → p = c → Case 2
T(n) = Θ(n1 · log1 n) = Θ(n log n)
a = 7, b = 2, p = 2, k = 0
log₂(7) = 2.807 → p < c → Case 1
T(n) = Θ(n2.807) = Θ(n2.807)
a = 1, b = 2, p = 1, k = 0
log₂(1) = 0 → p > c → Case 3
T(n) = Θ(n1) = Θ(n)
a = 3, b = 2, p = 1, k = 0
log₂(3) = 1.585 → p < c → Case 1
T(n) = Θ(n1.585) = Θ(n1.585)
Frequently Asked Questions
Because the per-level work in the recursion tree depends on both a and b. At level i, there are ai nodes each processing a subproblem of size n/bi. The total work at that level is ai · (n/bi)p = np · (a/bp)i. The ratio a/bp determines whether the series grows or shrinks, and a/bp < 1 is the same as a < bp, which is the same as logba < p. So logba and p are the natural quantities to compare.
In exact mathematics, Case 2 requires p = logba precisely. If p differs by any positive amount ε (no matter how small), the recurrence falls into Case 1 or Case 3. In practice, with floating-point inputs, the calculator uses a small tolerance (1e-9) to decide equality. If you are working with a fractional exponent that should mathematically equal logba — say, T(n) = 4·T(n/2) + n² where log₂(4) = 2 exactly — the tolerance catches it. If you enter a case like p = 2.0000001 with logba = 2, it correctly reports Case 3.
Yes — set p = 1 and k = 1. The calculator handles the extended form f(n) = np · logk n. A subtle point: the standard Master Theorem is often stated only for f(n) = np, and the log factor must be handled with the extended version. When p = logba and k > 0, the result is Θ(nc · logk+1 n) — the extra log factor comes from the additional level of summation that the log introduces. For example, T(n) = 2T(n/2) + n log n gives Θ(n log² n).
Four common cases: (1) the subproblems have unequal sizes, like T(n) = T(n/3) + T(2n/3) + n — use Akra–Bazzi instead; (2) the branching factor a is not constant; (3) f(n) is not polynomially bounded, like f(n) = 2n or f(n) = n!; (4) the gap between p and logba is not polynomial — for example, T(n) = 2T(n/2) + n log n technically has p = 1 and c = 1, but the standard theorem still handles it via the extended form with k = 1. When the theorem does not apply, fall back to the recursion-tree method, the substitution method, or the Akra–Bazzi formula.
Because when a = bp, the per-level work ai · (n/bi)p simplifies to np at every level. There is no geometric decay to make one level dominate, so every level contributes equally. Since there are logbn levels and each contributes np work, the total is np · logbn = Θ(np log n). The base of the logarithm is absorbed by the Θ notation, since changing base only changes the log by a constant factor.
Case 3 requires a·f(n/b) ≤ c·f(n) for some constant c < 1 and all sufficiently large n. This condition ensures that the work at deeper levels actually shrinks, so the sum of the series is dominated by the root. For f(n) = np, the condition is a·(n/b)p ≤ c·np, which simplifies to a/bp ≤ c. Since we are already in Case 3, p > logba means a/bp < 1, so we can always choose c = a/bp + ε < 1. The regularity condition is therefore automatically satisfied for polynomial f(n), which is why most textbooks do not mention it. It matters only for exotic f(n) functions that oscillate.
Variables
| Symbol | Quantity | Unit |
|---|---|---|
| a | Number of subproblems | |
| b | Factor by which input size is divided | |
| f(n) | Cost of dividing and combining |
What it means
The master theorem is a mathematical tool for analyzing the time complexity of divide‑and‑conquer algorithms. Given a recurrence of the form T(n) = a T(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is the cost of dividing and combining, the theorem provides three cases to determine the asymptotic bound. Case 1: if f(n) = O(n^(log_b a - ε)) for some ε>0, then T(n) = Θ(n^(log_b a)). Case 2: if f(n) = Θ(n^(log_b a) log^k n), then T(n) = Θ(n^(log_b a) log^(k+1) n). Case 3: if f(n) = Ω(n^(log_b a + ε)) and the regularity condition holds, then T(n) = Θ(f(n)). This theorem is essential for quickly deriving complexities of algorithms like merge sort (T(n)=2T(n/2)+n → Θ(n log n)), binary search (T(n)=T(n/2)+1 → Θ(log n)), and Strassen’s matrix multiplication. It simplifies the analysis, saving time over iterative expansion. The master theorem is a staple in algorithm analysis and is typically taught in computer science curricula.
Worked example
Master Theorem – Two Examples
Real‑World| Parameter | Value |
|---|---|
| a | 2 |
| b | 2 |
| f(n) | n |
| logba | log₂2 = 1 |
| Parameter | Value |
|---|---|
| a | 4 |
| b | 2 |
| f(n) | n |
| logba | log₂4 = 2 |
Common mistakes
- Applying to non‑divide‑and‑conquer recurrences: The master theorem only applies to recurrences of the form T(n)=aT(n/b)+f(n) with constant a≥1, b>1.
- Case selection: Identify which of the three cases applies based on f(n) relative to n^(log_b a) – mis‑classification leads to wrong Θ.
- Polynomial vs. non‑polynomial: If f(n) is not polynomially comparable, the theorem does not apply; use other methods (e.g., recursion tree).
- Base case ignored: The theorem gives asymptotic bounds; the base case affects only constants.
- Regularity condition: For case 3, check that a·f(n/b) ≤ c·f(n) for some c<1 and large n – otherwise the theorem fails.
Applications
The master theorem provides a systematic way to solve recurrence relations of the form T(n) = aT(n/b) + f(n), which arise from divide‑and‑conquer algorithms. It gives asymptotic bounds (Θ, O, Ω) for algorithms like merge sort, binary search, and matrix multiplication. This theorem is a cornerstone of algorithm analysis, enabling engineers to quickly determine the efficiency of recursive algorithms without deriving the full solution. Its applications extend to designing efficient algorithms for problems such as maximum subarray, closest pair of points, and fast Fourier transforms. In practice, understanding the master theorem helps in comparing algorithm alternatives, optimising parameters (e.g., choosing the base case size), and predicting performance on large inputs. It is an essential tool for any computer scientist or software engineer working on complex computational problems.
- Analysis of divide‑and‑conquer algorithms (merge sort, quick sort)
- Algorithm design and optimisation
- Comparison of recursive strategies
- Theoretical computer science and complexity classes
- Performance prediction for large‑scale data processing
Related calculators · Algorithms
Recently updated formulas
Suggest an improvement
Found a mistake? Have a better example? Let us know.
You may send up to 3 suggestions per 24 hours.