Derive a bound and validate its shape
For each recurrence, write the subproblem size at depth d, number of nodes, cost per node, and stopping depth. This makes hidden assumptions visible.
A: T(n) = 2T(n/2) + n
B: T(n) = T(n/2) + n
C: T(n) = T(n-1) + 1
A has linear work per level across logarithmic levels: Θ(n log n). B has a geometric sum n+n/2+n/4+...: Θ(n). C has linear depth and constant work per level: Θ(n). The same final bound for B and C does not imply the same stack requirement: their depths differ.
Acceptance checks
Implement operation counters for each recurrence over small valid inputs, rather than doing expensive real work. Compare observed ratios when doubling n. Include a clear base case to avoid zero-sized recursion continuing indefinitely.
Extension: add an allocation at every call and reason separately about peak live memory and cumulative allocation. A depth-first execution does not keep every historical allocation alive.
Check: explain why measuring only recursion depth would misclassify recurrence A's total work.