Motivation
A divide-and-conquer algorithm spends work on the current input, solves smaller subproblems and combines their answers. A recurrence tree separates the total work by depth. Depending on how the number of subproblems compares with their decreasing sizes, the root, the leaves, or all levels together can dominate the cost.
The result here is a deliberately restricted master theorem: subproblems have exactly equal sizes, the toll is a positive constant times a power, and input sizes are powers of the divisor. Floor and ceiling effects, unequal sizes and logarithmic tolls require additional arguments. These restrictions make the calculation exact and expose why the three cases arise.
Definitions
Definition 1.5.1
(Divide-and-conquer recurrence)
Fix integers and , a real , and constants . For with integer , let
The term is the nonrecursive work at a node of size and is the cost of a leaf. Write , so that . Asymptotic statements hold for through powers of , with the parameters fixed.
Theorems
Theorem 1.5.2
(Exact level sum)
For every and ,
For the sum is empty and the identity reads .
Theorem 1.5.3
(Three growth regimes)
Under these hypotheses,
The base of the logarithm is immaterial in the asymptotic notation.
Proof sketch or proof idea
Proof
(Level sums and the three regimes)
At depth , there are nodes, each of size . Their total toll is . The recursion reaches size one at depth and has leaves, each costing . Adding the costs gives the identity. Equivalently, induction on proves it by substituting the recurrence and shifting the sum's index.
Let . If , the internal-level sum is at least and at most for . It contributes . The leaf cost is because . If , every internal level costs and there are such levels. The leaves contribute , so the total is .
If , the geometric sum is for fixed . Moreover . Both the internal work and the leaves are , while the positive leaf term is already . This proves the last case. Positive toll and base costs prevent cancellations and supply the lower bounds used here.
Proof X-ray
Compare whole levels
The relevant ratio is : the number of nodes grows by per level, but the work at each node falls by a factor . Counting only one of these changes misses the competition.
The hypotheses enter at specific places. Fixed , and make a constant, so the geometric sum is , or with constants that do not depend on . Positive and supply the lower bounds, since no term can cancel another. The restriction makes every level size exact. The last case closes through the identity , which identifies the largest level cost with the leaf level.
Worked examples
Worked example 1.5.4
(Leaf-dominated work)
For with positive constant base cost, , , and . Since , the total is . Internal level costs double at each depth and the leaves contribute order .
Worked example 1.5.5
(Equal work at each level)
For , every internal level costs . There are such levels and leaves, so the total is , not merely .
Worked example 1.5.6
(Root-dominated work)
For , the ratio of successive level costs is . The root contributes and all internal levels together contribute less than ; the leaves contribute order . Therefore the total is .
Common mistakes
Counterexample mode
A level cost is not the total
In , observing that one level costs does not prove the total is linear. There are logarithmically many equally expensive levels, producing the extra factor .
Common mistake
(Applying the three cases outside their hypotheses)
The theorem does not directly apply to , where the subproblem size is not , or to , where the toll is not a fixed constant times . Both can be analyzed by other sums; substituting them into these three cases without a proof is invalid.
Common mistake
(Treating a logarithm in the toll as a constant)
For one may be tempted to take , see , and answer . The toll is not a constant times a power. At depth the nodes each pay with , so the internal cost is and ; for instance when .
Expanding a small tree
The level formula can be checked by writing the first few substitutions. Suppose and . Then
At the first three internal levels the costs are . The multiplicity and subproblem size together produce the level cost . This is different from following a single root-to-leaf path, which sees only one of the many subproblems at each level.
Worked example 1.5.7
(An exact calculation at size eight)
For and , the level costs for are , and , followed by leaves of cost one. Thus . Direct substitution agrees: , , and . The leaf cost must be counted consistently with the base case.
The number of leaves is , not generally . It equals in the familiar case , but for it is . The total number of all nodes is another geometric sum, when ; it does not alone determine the running time because node costs depend on their sizes. When , the recursion tree is a single path with nodes.
Concept lensAlgebraic
The level sum as a first-order linear recurrence
Put and . The recurrence becomes , with homogeneous solution and forcing term . If , then with , and the larger of and wins: leaves if , root if . If the forcing term resonates with the homogeneous solution and ; the factor is the extra logarithm. For this gives and .
A substitution proof and its limits
A recurrence tree suggests a bound; induction can verify a proposed one. For example, on powers of two let and . The exact formula is . It holds at . If it holds at , then
Thus the expression holds at every power of two. This proof checks both the base and the inductive step; it does not assert anything about values outside the recurrence's declared domain.
For a looser asymptotic upper bound, an induction hypothesis sometimes needs a lower-order correction to close. Blindly assuming at every size can fail at the base because while . One can instead use a sufficiently large threshold, add a linear term, or use ; each choice must be verified. A successful induction is a proof for the stated range and constants, not merely a guess suggested by a tree picture.
The exact identity also clarifies lower bounds. The root contributes and the leaves contribute , so each is a lower bound when costs are nonnegative. In the equal-level case neither alone supplies the extra logarithm; summing all nonnegative level costs does. If a model allowed negative tolls or cancellation, these lower-bound arguments would require different hypotheses.
A separate floor-and-ceiling example
Consider the recurrence defined for every positive integer by and
where . This recurrence is not covered directly by the exact equal-size theorem for arbitrary , but its tree can be bounded independently. Every internal node splits its size into two positive integers whose sum is the parent size. There are exactly leaves of size one. All nodes at depth have size at least two, so their sizes sum to and that level costs . No root-to-leaf path has more than internal levels, and the sizes of nodes at any level sum to at most . Therefore
which proves for .
To justify the depth statements, after balanced splits every present subproblem has size either or . This follows by induction from splitting each size into its floor and ceiling halves. Before the smaller size is at least two; by every remaining size is one. This argument handles uneven last levels rather than pretending that every branch has the same depth.
Worked example 1.5.8
(An uneven split)
For , the first split has sizes and . The next split produces sizes from the size-two node and from the size-three node. One size-two node needs a further split. There are five leaves, while the internal level sizes sum to , then , then . The total toll is and the leaf cost is ; the floor-and-ceiling bound encloses this value.
From a recurrence to an algorithmic claim
A recurrence must match the algorithm being analyzed. Count how many recursive calls are made, what sizes they receive, and what work remains outside those calls. A binary search performs one recursive call on roughly half the input, not two; merge sort performs two calls and linear combining work. If a call stops early on some inputs, the exact recurrence may instead be a worst-case bound. The mathematical solution of a recurrence is useful only after its relation to the implementation has been established.
The toll is a cost under a chosen model. Counting comparisons, arithmetic operations, allocations, or bit operations can lead to different recurrences. A constant-time arithmetic assumption may be inappropriate for integers whose bit lengths grow with the input. Similarly, a recurrence describing total work does not automatically describe peak memory or parallel running time: those quantities combine recursive calls differently.
Checking boundary cases
When and , the tree is a single chain with constant toll at each internal node. Its length is , and the equal-level formula gives . When and , the toll decreases geometrically down that chain and the root dominates. When , the exact sum has no internal terms and returns the base cost. The asymptotic expression need not be positive at ; describes sufficiently large inputs, not an exact formula at every size.
If constants in a claimed recurrence depend on , the geometric comparison may change. The theorem fixes as the input size grows. For instance, treating a slowly growing factor such as as a constant changes the toll and can lose an entire logarithm. Writing the assumptions before applying a named theorem is often the quickest way to catch such mistakes.
A logarithmic toll outside the theorem
The same level method can solve some recurrences outside the three-case statement, but the level sum must be recalculated. Let and, on powers of two, . At depth , the subproblems each have size and logarithm . Their total toll is therefore . The internal cost is
and the leaves add . Hence for large powers of two. Treating the logarithm in the toll as a constant would incorrectly give .
This derivation is a new calculation, not an application of the stated power-toll theorem. It illustrates a general strategy: write the work of one node at depth , multiply by the number of nodes at that depth, determine the exact stopping depth, and sum. If those quantities depend on the path or inputs have unequal sizes, a single uniform level formula may no longer exist. One can still bound the tree, as in the floor-and-ceiling example, but the bound must be justified for that recurrence.
The recurrence-tree picture describes the arithmetic sum of costs even when an implementation reuses memory between recursive calls. It does not say that all nodes exist in memory simultaneously. Conversely, a parallel implementation may evaluate independent calls at the same time, so its elapsed time depends on the critical path and scheduling rather than simply on total work. State which resource the recurrence represents before interpreting its solution.
A final arithmetic check
For the root-dominated example with , the exact sum gives
The formula holds at and substituting it into the recurrence reproduces it at larger powers of two. In particular, its leading term is positive and quadratic. Exact calculations on a few small inputs can catch a misplaced leaf term or wrong level ratio, although finitely many checks do not prove an asymptotic bound for all inputs.
Summary
The level ratio compares the growth in node count with the decrease in work per node. A decreasing geometric series is root-dominated, equal level costs accumulate a logarithm, and an increasing series is leaf-dominated. The exact level identity proves these claims under the stated hypotheses.
Exercises
Quick check
(Classify on powers of two, with positive constant base cost.)
Solution · Answer
Here and , so .
Quick check
(Classify on powers of two.)
Solution · Answer
Here with , so for large powers of two.
Quick check
(Classify on powers of three.)
Solution · Answer
Here , so .
Quick check
(How many leaves occur for when ?)
Solution · Answer
The tree has depth and leaves.