Recurrence lab

📈 Check: recursion vs closed form

Dots: T(n) computed by running the recurrence itself. Line: the closed form from the substitution. If the algebra is right they agree exactly.

🏛️ Master Theorem calculator

For T(n) = a·T(n/b) + f(n) with f(n) ∈ Θ(nᵈ), d ≥ 0 (Levitin §5.1). Compare a with bᵈ.

How to read this

• Tree: each circle is one call; the number inside is its input size and the small number under it is the non-recursive work that call does itself (its f(size)). Green circles are base cases: their number is the initial condition.
• Right column: for each level, (number of calls) × (work per call) = level sum. The total cost T(n) is the sum of that column.
• Backward substitution panel: the highlighted row is the algebra matching the current level. Row i of the algebra "opens up" level i of the tree.
• Pseudocode: the highlighted lines are the ones responsible for the cost you are looking at: the recursive calls when a new level appears, the local work when a level is costed, the base case at the leaves.
• For divide recurrences the size slider picks k, with n = bᵏ, so every division is exact (the "smoothness rule" lets us do this).

Try this

1. The classic exam recurrence (Practice Exam 1, Problem B4). Load T(n) = T(n/2) + log₂ n. Before playing, write the first two substitutions yourself. Then check: T(n) = 1 + log₂n·(log₂n + 1)/2, so Θ(log² n). For n = 16: 1 + 4·5/2 = 11.
2. Load mergesort and watch the level sums: every level costs exactly n. How many levels have work? (log₂ n.) That is n log₂ n in one picture.
3. Load Hanoi: each level has twice the cost of the level above, so the bottom level alone is about half the total. Predict the total for n = 6 (63).
4. Custom: a = 4, b = 2, d = 1. Predict the Master Theorem case before classifying. Then watch the tree: the level sums grow ×2 per level, so the leaves dominate: Θ(n²).
5. Custom: a = 2, b = 2, d = 2. Now the sums shrink by half each level: the root dominates, Θ(n²).