The Master Theorem — Recursion Tree & Case Detector

Enter a, b, and f(n)=nc. Watch the recursion tree grow level by level; each level's work ai·f(n/bi) is a bar. Whether the bars grow (leaves win), stay flat (tie), or shrink (root wins) reveals the case.

level 0

Recursion tree (level by level)

leaves dominate (Case 1) all levels tie (Case 2) root dominates (Case 3)

Per-level work   ai·f(n/bi)

critical exponent log_b a1.000
watershed n^(log_b a)n^1.00
geometric ratio r = a/b^c1.000
Press Step to reveal levels one at a time.
The Master Theorem compares the combine cost f(n)=n^c to the watershed n^(log_b a). Each tree level i does total work a^i · f(n/b^i). Summing them is a geometric series with ratio r = a/b^c.

The three cases at a glance

Case 1 (r>1) f polynomially smaller than watershed → leaves dominate → T(n)=Θ(n^log_b a)
Case 2 (r=1) f equals watershed → all levels tie → T(n)=Θ(n^log_b a · log n)
Case 3 (r<1) f polynomially larger (+regularity) → root dominates → T(n)=Θ(f(n))
Gap cases: when f differs from the watershed by only a log factor, r→1 and the series does not collapse — the basic theorem is silent. Use the extended Case 2 (adds one log) or Akra–Bazzi (the integral form) instead.
Self-contained visualization. The tree is drawn schematically (capped node count) but the per-level work bars use the exact values a^i · (n/b^i)^c. r > 1 → bars grow → leaves win (Case 1). r = 1 → bars flat → tie (Case 2, extra log factor). r < 1 → bars shrink → root wins (Case 3). See junior.md, middle.md, and professional.md for the full derivation.