ToolSphere
Back to all articles
student

Master Theorem: 10 Solved Examples

2026-10-176 min read

Try it: free Master Theorem Calculator

Find running-time bounds for divide-and-conquer recurrences

Open →

The master theorem solves recurrences of the form

T(n) = a·T(n/b) + f(n)

where a divide-and-conquer algorithm makes a recursive calls on inputs of size n/b and does f(n) work to split and combine. You don't need to unroll anything: compare f(n) with one number and read off the answer.

The one comparison

Compute the critical exponent log_b(a). The recursion alone produces n^(log_b a) leaves of work; the question is whether f(n) is smaller, about equal, or larger.

Case When Answer
1 f(n) grows polynomially slower than n^(log_b a) T(n) = Θ(n^(log_b a))
2 f(n) = Θ(n^(log_b a) · logᵏ n) T(n) = Θ(n^(log_b a) · logᵏ⁺¹ n)
3 f(n) grows polynomially faster, and a·f(n/b) ≤ c·f(n) for some c < 1 T(n) = Θ(f(n))

With k = 0, case 2 is the familiar "equal" case: Θ(n^(log_b a) · log n). The extended version with k > 0 is what solves recurrences like 2T(n/2) + n log n, which the basic three cases can't.

Ten solved examples

Recurrence a, b log_b a f(n) Case T(n)
T(n) = 2T(n/2) + n (merge sort) 2, 2 1 n 2 Θ(n log n)
T(n) = T(n/2) + 1 (binary search) 1, 2 0 1 2 Θ(log n)
T(n) = 3T(n/2) + n (Karatsuba) 3, 2 1.585 n 1 Θ(n^1.585)
T(n) = 7T(n/2) + n² (Strassen) 7, 2 2.807 n² 1 Θ(n^2.807)
T(n) = 8T(n/2) + n² 8, 2 3 n² 1 Θ(n³)
T(n) = 4T(n/2) + n 4, 2 2 n 1 Θ(n²)
T(n) = 2T(n/2) + n² 2, 2 1 n² 3 Θ(n²)
T(n) = T(n/3) + n 1, 3 0 n 3 Θ(n)
T(n) = 3T(n/4) + n log n 3, 4 0.792 n log n 3 Θ(n log n)
T(n) = 2T(n/2) + n log n 2, 2 1 n log n 2 (k = 1) Θ(n log² n)

Two worked in full

Strassen, T(n) = 7T(n/2) + n². log₂ 7 ≈ 2.807. f(n) = n² is polynomially smaller than n^2.807 (by a factor of n^0.807), so case 1 applies: the leaves dominate, and T(n) = Θ(n^log₂7) ≈ Θ(n^2.807). That is why Strassen beats the ordinary Θ(n³) matrix multiplication (the 8T(n/2) + n² row).

T(n) = 2T(n/2) + n². log₂ 2 = 1, and f(n) = n² is polynomially larger than n¹. Check the regularity condition: a·f(n/b) = 2·(n/2)² = n²/2 ≤ ½·n², so c = ½ works. Case 3: the top level dominates, T(n) = Θ(n²).

When the master theorem doesn't apply

  • The subproblems aren't equal sizes, e.g. T(n) = T(n/3) + T(2n/3) + n. Use a recursion tree or the Akra–Bazzi method.
  • The recurrence subtracts instead of divides, e.g. T(n) = T(n − 1) + n (that's Θ(n²), by unrolling).
  • a < 1, or b ≤ 1: not a divide-and-conquer recurrence.
  • f(n) falls between the cases in the basic theorem, e.g. 2T(n/2) + n/log n. Neither the basic nor the extended version above covers that one.

Common mistakes

  • Comparing f(n) with n^a or n^b instead of n^(log_b a).
  • Calling it case 3 without checking regularity. For ordinary polynomial f(n) it always holds, but say so.
  • Forgetting the extra log in case 2. f(n) = n with log_b a = 1 gives n log n, not n.

Try it

The master theorem calculator takes a, b and f(n) = nᶜ · logᵏ n, shows the critical exponent, picks the case and explains why, including the extended case-2 form for n log n terms.

Use the Huffman Coding Calculator to work through a related algorithms exercise. For a related walkthrough, read Huffman Coding Example, Step by Step.

Looking for other tools?

Explore ToolSphere Homepage →