Motivation
The exact recurrence-tree calculation for a power toll shows three possible sources of dominant work. Real algorithms often have a toll known only up to asymptotic bounds, or include a logarithmic factor. A more general theorem handles those cases, but its hypotheses cannot be omitted: a large root toll alone does not prevent a smaller subproblem from having an even larger toll if the toll oscillates.
We prove a common form on powers of the divisor. The theorem is not a blanket rule for unequal subproblem sizes or arbitrary floor and ceiling recurrences. The companion recurrence-tree unit treats one balanced rounding example separately.
Definitions
Definition 1.4.1
(Recurrence on powers of the divisor)
Fix integers , , and set . For , , let and
where is nonnegative on these powers. All asymptotic bounds are as with and the constants in the hypotheses fixed. Write for any fixed base greater than one.
Definition 1.4.2
(Regularity condition)
The regularity condition used in the third case is that for some and all sufficiently large powers of ,
It compares the total toll of a node's children with that of the node, rather than merely comparing with a power at the root.
Theorems
Theorem 1.4.3
(Master theorem on powers of the divisor)
Under the definitions above:
- If for some , then .
- If for a fixed , then .
- If for some and the regularity condition holds, then .
Theorem 1.4.4
(A level-sum identity)
For , the exact recurrence gives
Proof sketch or proof idea
Proof
(Level sums for the identity and the three cases)
Expansion gives nodes of size at level and leaves, proving the identity. Since , the leaves already give a positive lower bound of order .
In case 1, after enlarging a constant to cover the finitely many small powers, each level is at most
Summing over gives because it is bounded by a convergent geometric series. The leaves supply the matching lower bound.
In case 2, ignore the finitely many lowest-size levels where the asymptotic inequalities need not yet apply. At level in the remaining range, the total toll is between constant multiples of . For fixed , : the upper bound is and the last half of the terms give a matching lower bound up to a constant. The omitted small-size levels and leaves contribute only , so .
In case 3, apply regularity while subproblem sizes are above its threshold. The total toll at depth is at most , so these levels sum to . Once sizes fall below the fixed threshold, the remaining subtree cost per node is bounded by a constant because only finitely many power-of- sizes are involved. There are at most a constant multiple of such nodes, whose total cost is . The root toll gives , proving the matching lower bound.
Proof X-ray
What regularity controls
Case 3 uses its two hypotheses for two different parts of the sum. The gap makes the leaf contribution negligible next to , which is what allows the answer to be rather than a sum of two terms. Regularity controls the other part: it says that the combined toll of each generation is at most a fixed fraction of the previous generation, so the level sum is a convergent geometric series dominated by its first term. The gap alone only compares the root toll with ; it says nothing about whether a later generation's toll exceeds the root's, as the oscillating example below shows. The matching lower bound is the easy step, because the root toll is itself one term of the sum.
Worked examples
Worked example 1.4.5
(Smaller toll)
For , and . Case 1 gives .
Worked example 1.4.6
(A logarithmic toll)
For , and . Case 2 gives . This extends the exact level calculation in the companion unit.
Worked example 1.4.7
(Regular root-dominated work)
For , , and . The regularity condition holds with , so case 3 gives .
Common mistakes
Counterexample mode
A large toll without regularity
For , define when is even and when is odd. It always satisfies , but at odd the two child tolls total , much larger than the root toll . Thus is not along those powers. The regularity condition cannot simply be dropped from case 3.
Common mistake
(Applying the theorem to rounded recurrences)
A theorem on powers of does not automatically prove the same bound for an arbitrary rounded recurrence. A separate comparison or tree argument is needed.
Common mistake
(Using a negative logarithm exponent in case 2)
The second case requires the stated fixed . Substituting a negative exponent needs a new summation argument, as the harmonic example below shows.
Finding the critical exponent
The exponent describes the number of leaves: . It is the reference scale against which the nonrecursive toll is compared. It need not be an integer. For instance, if and , then . A toll is polynomially smaller than , while is polynomially larger. The comparisons must be made using an actual positive exponent gap, not merely by observing a numerical difference at a few inputs.
The constants hidden in the asymptotic notation are fixed for a given recurrence. In case 1 there must be a fixed and a constant such that for every sufficiently large permitted size. In case 3 there must similarly be a fixed positive gap and a regularity factor strictly below one. A factor that approaches one with does not satisfy the stated regularity condition with a single fixed .
Worked example 1.4.8
(A noninteger critical exponent)
For on powers of two, . Choose any fixed with ; then , and case 1 gives . It would be incorrect to round to two and report a quadratic bound as the tight result.
Inspecting the level sum
The exact expansion separates the proof from any named case. At level , the factor counts nodes and the argument is the size at each node. The base term is , not another application of unless the recurrence explicitly defines it that way. For the sum is empty. These conventions avoid double-counting the leaves.
In the matching-toll case, put . The total cost of a level with sufficiently large subproblem size is proportional to . The levels near the root have large , while those near the leaves have small . Summing all of them gives a power sum. When , each relevant level contributes order and the number of levels supplies one logarithm. When , the level costs form an arithmetic progression and their sum supplies two logarithms.
The condition makes the elementary power-sum estimate used in this theorem immediate. Other exponents can have different behavior. For example, define for . It is smaller than by a logarithmic factor, but it is not for any fixed . The level identity gives , or for large powers. The harmonic sum bound follows by comparison with . This example shows why "smaller than " is not enough for case 1.
Understanding regularity
The inequality says that the sum of the tolls at the children of a node is at most a fixed fraction of that node's toll. Applying it repeatedly makes total level tolls decrease geometrically until the subproblem size drops below the threshold. The bounded final subtree contribution is handled separately; regularity need not hold at the base size itself.
In the oscillating counterexample, the issue is not a negative toll or a strange base case. Every toll is positive and at least , but along odd powers of two the child subproblems land on even exponents with much larger cubic tolls. This makes the next level exceed the root by an unbounded factor. An asymptotic lower bound on alone does not compare consecutive levels and therefore cannot establish root domination.
A regularity check should be written with the actual function and the actual arguments. For with , compute . The ratio is a fixed , so works. Stating that "looks large" omits the condition the proof needs. For a function with several terms or oscillation, the ratio can require more careful analysis.
Asymptotic bounds versus exact costs
The theorem provides upper and lower asymptotic bounds, not exact constants or exact values for small inputs. A direct expansion can still be useful for checking an implementation or a proposed formula. If and on powers of two, the exact calculation gives . It is consistent with case 3, but the theorem alone would not determine the coefficient two or the lower-order term.
If is only known as an upper bound on an algorithm's per-call work, solving an upper-bound recurrence does not by itself prove a matching lower bound on that algorithm. A tight claim needs appropriate lower bounds on the algorithm or an exact recurrence with nonnegative work. Likewise, a recurrence for total work does not automatically bound peak space or parallel elapsed time; the recursive subproblems may share or overlap those resources differently.
Rounding and applicability
Many programs divide an arbitrary input into subproblems of sizes and . The proof above assumes the exact same size at every node and a common stopping depth. Rounding can often be controlled, but the required bounds depend on the recurrence and base cases. A balanced two-way split with linear toll is proved separately in the recurrence-tree unit; that specific argument is not a proof for every rounded recurrence.
Before invoking this theorem, check the number of recursive calls, divisor, toll, fixed parameters, base case and input domain. A recurrence such as has a different shape. A recurrence with two unequal subproblem sizes likewise cannot be forced into the same parameters without a comparison proof. Matching the theorem's hypotheses is part of the solution, not an optional formality after naming a case.
A complete case-selection calculation
Consider for powers of three, with a positive constant base cost. First compute . For large , , so the toll is . Case 2 applies with and gives . The constant factor between logarithm bases does not affect the conclusion. The term ensures a positive toll near the base, but the asymptotic classification depends on large inputs.
Now consider . Again , but the toll is polynomially larger. Compute the regularity ratio: . Thus works and case 3 gives . Writing both the exponent comparison and the ratio check prevents the root-dominated conclusion from being based on only one hypothesis.
The two examples also show why the same branching factor can lead to different total costs. In the first, the number of nodes cancels the quadratic decrease in each node's power term, leaving a logarithmic toll at every level. In the second, each successive level costs a fixed fraction of its predecessor. The theorem packages these level calculations but does not remove the need to identify the right toll.
A check on the small-size tail
In case 3, the first level below the regularity threshold need not consist of leaves. Its nodes can have several further generations before size one. The threshold is fixed, however, and only finitely many powers of lie below it. The maximum complete subtree cost among those sizes is therefore a constant for the fixed recurrence. Multiplying that constant by the number of nodes at the boundary gives the required tail. This explicitly accounts for base work without applying regularity where it has not been assumed.
Summary
The level identity reduces the recurrence to a sum of tolls. A polynomially smaller toll is dominated by leaves, a matching power accumulates a logarithmic sum, and a polynomially larger regular toll is dominated by the root. Regularity is a hypothesis with a concrete purpose.
Exercises
Quick check
(Apply the theorem to .)
Compute first and compare it with the exponent of the toll.
Solution · Answer
Here and the toll is polynomially smaller, so .
Quick check
(Apply the theorem to .)
Compute and decide which case the toll matches.
Solution · Answer
Here , and the toll matches , so .
Quick check
(Check regularity for .)
Compute and compare it with .
Solution · Answer
We have ; regularity holds with and the result is .
Quick check
(Why do the leaves give a lower bound of order ?)
Count the leaves and their individual cost.
Solution · Answer
There are leaves, each of positive cost .