DSA II · Work by level

Divide & Conquer Recurrence Tree

Expand a balanced recurrence one level at a time. Track the number of subproblems, their sizes, the work per node, and the total work at each level. Compare that exact finite sum with its asymptotic growth.

Example

Recursive calls a

Shrink factor b

Exponent c in f(n)

Log exponent k

Depth L · input n = bᴸ

Model: T(1) = 1; internal-node work is exactly f(n) = nᶜ(logᵦ n)ᵏ. Choosing n = bᴸ avoids rounding subproblem sizes. Reset hides the expansion again.

Playback speed · slow → fast

Recurrence and current step

Recursion tree

Large levels are collapsed into a labeled group. The number of nodes and all cost totals still include every recursive call. Arrows into a group represent the collection of calls, not a single parent-child edge.

Work by level

Level d	Nodes aᵈ	Size n / bᵈ	Cost / node	Level cost

T(n) = Σ[d = 0 … L − 1] aᵈ f(n / bᵈ) + aᴸT(1)