ToolSphere

Master Theorem Calculator

Computer science

Solve divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n) using the Master Theorem. Identify matching cases and asymptotic big-Theta bounds.

Master theorem calculator

Classify T(n) = a·T(n/b) + f(n), where f(n) = nc·(log n)k, into its Θ bound.

Case 2

Θ(n · log n)

Critical exponent logb(a) = 1.000. f(n) grows at the same rate as n^1, so every level of the recursion tree contributes equally, adding one extra log factor.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Master Theorem Calculator

  1. 1Write the recurrence as T(n) = a·T(n/b) + n^c·(log n)^k before entering its parameters.
  2. 2Enter a for the number of subproblems and b for the factor by which each subproblem shrinks.
  3. 3Enter c for the polynomial exponent and k for the logarithm exponent. Use k = 0 when there is no log factor.
  4. 4Read the critical exponent, matching case and Θ bound; keep the exact logarithm in a written proof if the displayed exponent is rounded.
  5. 5Compare the loaded merge-sort example with binary search, Strassen or the log-factor preset. Check that your homework recurrence fits the supported form.

About Master Theorem Calculator

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.

Guides and tutorials

Frequently asked questions

How do I use a master theorem calculator?

Rewrite the recurrence in the supported equal-subproblem form and enter a, b, c and k. Read the critical exponent, compare it with c and report the displayed case and Θ bound with the theorem assumptions.

What is the critical exponent log_b(a)?

It is log(a) divided by log(b), the exponent associated with the recursion-tree leaf count. Comparing c with this exponent determines which case applies to the supported polynomial-times-log input.

Does this recurrence solver show work?

It shows the critical exponent, a case number and a short explanation of the growth comparison. It does not draw the recursion tree or calculate an exact sequence of T(n) values.

Can the master theorem handle n log n?

This calculator supports a nonnegative logarithm power through k. When the polynomial exponents match, the generalized case adds a logarithm power; check whether your course allows that theorem version.

What do I enter when there is no log factor?

Enter k = 0, which makes the logarithmic factor equal to one. Enter the polynomial exponent separately in c, and fill every field before using the result.

Is the output Big O or Big Theta?

The output is a tight Θ growth class under the recurrence assumptions. Big O expresses an upper bound; a tight Θ result states both an asymptotic upper and lower bound.

Does case 3 need the regularity condition?

Yes: the recursive contribution to f(n) must eventually be bounded by a fixed fraction of f(n). For the supported family with c strictly above the critical exponent, that condition follows from a/b^c < 1.

Can it solve recurrences with unequal subproblem sizes?

No. All recursive calls must have the same n/b size in this input model. Use a method suited to unequal sizes rather than forcing the terms into one a and b.

Why is the Strassen exponent shown as a decimal?

The interface rounds the critical exponent for readability. Keep its exact logarithmic expression in a proof, because replacing an exact exponent with a rounded decimal is an approximation.

Can I paste an entire recurrence into the tool?

No, the interface takes separate numeric parameters. Identify the recursive-call count, shrink factor and nonrecursive exponents first, then compare the result with your own derivation.

Have a suggestion for Master Theorem Calculator?Share your feedback ↗