intro practice · coding problem
Solve a divide-and-conquer recurrence
Implement masterCase(a, b, fExp) for T(n) = a*T(n/b) + n^fExp. Let c = log_b(a). Return 'leaves' when fExp < c (leaf work dominates, T = n^c), 'balanced' when fExp === c (T = n^c log n), 'root' when fExp > c. Compare with a small tolerance — log_b(a) is floating point.
The mechanism
Trust the recursive call. You verify a base case and verify that the recursive step is correct ASSUMING the call on a smaller input is correct — that is induction, and it is why tracing the whole call tree in your head is both unnecessary and the main source of confusion. Every recursion also implies a recurrence, and the Master theorem reads it off directly: T(n) = aT(n/b) + f(n) is decided by whether the work at the leaves or at the root dominates.
Expected evidence
masterCase(2,2,1) -> 'balanced' (mergesort); masterCase(8,2,2) -> 'leaves'; masterCase(2,2,2) -> 'root'
Try this drill in the practice workspace →
Hints when you need them
- log_b(a) is Math.log(a)/Math.log(b) — do not assume it is an integer.
- Use a tolerance around 1e-9 for the equality case or mergesort will misclassify.
Watch for these mistakes
- Tracing execution instead of trusting the inductive hypothesis, then getting lost three levels deep
- A base case that does not actually terminate every path — off-by-one on the shrink step
- Recursing without shrinking the input, or shrinking it in a way that skips the base case
- Ignoring stack depth: an O(n) recursion on a million elements overflows where a loop would not