What the master theorem calculator solves
Use this recurrence solver when an Intro to Algorithms homework problem divides an input into equal-size recursive subproblems. It classifies T(n) = a·T(n/b) + f(n), with f(n) = n^c·(log n)^k, and displays the matching case, critical exponent and tight asymptotic bound. The loaded merge-sort example gives you a result immediately; editing a parameter updates the classification without a separate solve button.
The answer describes growth as input size increases. It does not predict elapsed seconds, count exact instructions or solve for a particular value of T(n). A Θ bound also assumes the usual constant-size base case with constant positive cost. Before using it on a midterm review problem, derive the recurrence from the algorithm rather than choosing parameters just because a familiar bound appears.
The formula and supported inputs
Let p = log_b(a) = log(a) / log(b). Compare the polynomial exponent c with p. Here a is the number of recursive calls, b is the shrink factor, c describes the nonrecursive polynomial work and k describes any logarithmic factor. The calculator accepts finite a ≥ 1, b > 1, c ≥ 0 and k ≥ 0. Negative logarithm powers and arbitrary expressions for f(n) are outside its input model.
For an actual algorithm, a normally counts whole recursive calls. The form T(n/b) means divide the problem size by b; it does not mean subtract b. Constant multipliers on f(n) do not change the asymptotic class, so you enter its exponents rather than its coefficient. A logarithm without a stated base is sufficient for this growth comparison because changing a fixed log base changes only a constant factor.
How the cases work
Case 1 applies when c < p by a fixed positive gap. The recursive leaves dominate and the bound is Θ(n^p). A fixed nonnegative logarithm power in f(n) does not overcome that polynomial gap. Compare exponents first; comparing only the visible size of terms at a small input can point you toward the wrong case.
Case 2 applies when c = p. For the supported k ≥ 0, the generalized result is Θ(n^p·(log n)^(k+1)). With no logarithm in f(n), the levels of the recursion tree contribute equal total work. With a positive logarithm power, level costs vary; summing them still introduces the extra log power. This distinction matters when explaining your reasoning rather than simply reporting a case number.
Case 3 applies when c > p, giving Θ(n^c·(log n)^k). It requires the regularity condition a·f(n/b) ≤ d·f(n) for a constant d < 1 and sufficiently large n. For this supported polynomial-times-log family under c > p, the ratio tends to a/b^c < 1, so the condition holds eventually. Do not extend that statement to arbitrary oscillating functions.
Worked examples from the solver
These outputs were computed with the same library used by the calculator. Select the corresponding preset or enter the table values to reproduce them.
| Recurrence | a | b | c | k | Case | Displayed bound |
|---|---|---|---|---|---|---|
| Merge sort: 2T(n/2) + n | 2 | 2 | 1 | 0 | 2 | Θ(n · log n) |
| Binary search: T(n/2) + 1 | 1 | 2 | 0 | 0 | 2 | Θ(1 · log n) |
| Strassen: 7T(n/2) + n² | 7 | 2 | 2 | 0 | 1 | Θ(n^2.807) |
| Log-factor example: 2T(n/2) + n log n | 2 | 2 | 1 | 1 | 2 | Θ(n · log² n) |
| Larger combine cost: 2T(n/2) + n² | 2 | 2 | 2 | 0 | 3 | Θ(n²) |
For merge sort, p = 1 matches c = 1, so the result adds a logarithmic factor to the linear combine cost. Binary search has p = 0 and constant nonrecursive work; the displayed factor 1 can be omitted in your final Θ(log n) answer. Strassen's critical exponent is approximately 2.807, greater than its combine exponent. Its exact mathematical exponent is log₂7; the interface rounds the displayed decimal, so retain the logarithm in a formal answer.
Reading the result in a course solution
A complete written solution identifies the parameters, computes p, states the exponent comparison and gives the resulting Θ class. If your course teaches only the basic version, explicitly name the generalized polylogarithmic case when f(n) contains log n. Follow the theorem statement your instructor provides instead of treating a calculator label as a substitute for its hypotheses.
The solver uses numerical comparisons and rounded display text. Do symbolic comparisons by hand when exponents are extremely close, and do not infer equality merely because their displayed decimals look identical. Use the worked master theorem guide for more recurrence practice and the sorting algorithms guide to connect bounds with algorithm behavior.
Common mistakes and limits
Do not enter the total running-time guess as f(n): that term includes only work outside the recursive calls. Do not confuse the number of calls with their size reduction. A recurrence that shrinks by subtraction or contains unequal recursive sizes does not fit this form; use unrolling, substitution, a recursion tree or an appropriate broader theorem instead.
Check that every field contains the intended numeric value before reading the answer. This page offers parameter inputs and presets, not a parser for a pasted recurrence, a recursion-tree diagram or an exact operation counter. For a different algorithms topic, the Huffman coding calculator lets you inspect a constructed code rather than an asymptotic recurrence classification.