📐 Master Theorem Calculator
Enter the parameters of a divide-and-conquer recurrence and get the log_b(a) comparison, the case that applies, and the tight Θ bound — the fast way to read off the complexity of a recursive algorithm.
🧩 Solve T(n) = a·T(n/b) + Θ(nᵈ)
📐 Master Theorem — Case 2
log_b(a) = 1 = d = 1, so work is spread evenly (Case 2).
What is the Master Theorem?
The Master Theorem is a cookbook for the running time of divide-and-conquer algorithms. Instead of expanding a recursion tree by hand, you plug the recurrence T(n) = a·T(n/b) + Θ(n^d) into a single comparison of log_b(a) against d and read off one of three closed-form answers.
It is the fastest route to the complexity of algorithms like merge sort, binary search, Karatsuba multiplication, and Strassen's matrix multiplication. This calculator does the log computation, picks the correct case, formats the tight Θ bound, and explains why — while validating that a ≥ 1 and b > 1 so you do not silently get a nonsense answer.
❓ Frequently Asked Questions
What recurrences does the Master Theorem solve?
It solves recurrences of the form T(n) = a·T(n/b) + f(n), where a ≥ 1 is the number of subproblems, b > 1 is the factor by which the input shrinks each level, and f(n) is the work done outside the recursive calls. This calculator takes f(n) = Θ(n^d), which covers the vast majority of divide-and-conquer analyses you meet in practice.
What are the three cases?
Compare log_b(a) with d. Case 1 (log_b(a) > d): the leaves dominate and the answer is Θ(n^{log_b a}). Case 2 (log_b(a) = d): work is spread evenly across levels and the answer is Θ(n^d log n). Case 3 (log_b(a) < d): the top-level work dominates and the answer is Θ(n^d).
Why does merge sort come out as Θ(n log n)?
Merge sort splits into a = 2 subproblems of half the size (b = 2) and does linear merging work, so d = 1. Here log_b(a) = log₂2 = 1, which equals d, so it lands in Case 2 and the tight bound is Θ(n log n). Enter a = 2, b = 2, d = 1 to see it.
When does the Master Theorem not apply?
It requires a ≥ 1, b > 1, and non-negative polynomial work, and it does not cover recurrences where the subproblems are unequal sizes, where f(n) is not polynomial (for example n log n sitting in the regularity gap of Case 3), or where a and b are not constants. This tool validates the a and b constraints and flags invalid input.