Motivation
A recurrence written with n divided by b often hides the fact that input sizes are integers. Replacing a ceiling by an exact fraction can change where recursion stops, especially at the smallest inputs. A proof should begin with the actual repeated rounded sizes and charge the final leaves as well as internal work.
The three usual growth regimes come from a geometric sum across levels. The equality case becomes more delicate when the toll includes a logarithm: an extra logarithmic factor is not always the right answer, and a reciprocal logarithm produces a different boundary.
The integer-size analysis below treats uniform fixed-branch recurrences with explicitly positive base and toll bounds. Unequal branches, arbitrary data-dependent branching and cancellation between negative costs are not consequences of these hypotheses.
Definitions
Definition 3.2.1
(A uniform rounded recurrence and its toll)
Fix integers , and a real exponent . Let the positive base value be . For integer , consider
where c,C are fixed positive constants. The a recursive calls all have the displayed rounded input size. This is a mathematical work recurrence; constants and bounds are independent of n.
Write . The ceiling recursion stops at size one, so a size-one call is a base case, not another recursive call. Empty-input work can be defined separately and never enters this positive-size recurrence.
Definition 3.2.2
(The floor version and its base convention)
For a floor version, use fixed positive bounded base values for every integer , and apply only for . There c and C bound the toll on that recursive range. This base convention avoids an undefined size-zero call.
All asymptotic constants may depend on a,b,d,c,C and the finitely many base values, but not on n. Arithmetic-operation versus bit-operation cost must already have been incorporated in g; the recurrence does not declare long arithmetic constant-cost by itself.
Theorem/Proposition
Theorem 3.2.3
(Ceiling recurrence: all three geometric regimes)
For the ceiling recurrence,
The recursion has exactly levels of internal expansion and leaves. The formulas also cover the chain case a equal to one and d zero, which gives logarithmic work rather than constant work.
Theorem 3.2.4
(Floor recurrence has the same growth orders)
Under the stated floor base convention and positive toll bounds, the same three asymptotic regimes hold. For n at least one, its depth is , and each leaf has a size from one through b minus one.
No monotonicity of an unspecified unknown work function is needed: the actual rounded subproblem sizes can be bounded directly at each level.
Theorem 3.2.5
(Critical logarithmic tolls have three further thresholds)
On exact powers , suppose instead that , the same positive base is used, and
at recursive power inputs, with real r. Then as L tends to infinity,
The base and finitely many small powers are handled separately, so no logarithm of zero is evaluated. This statement is restricted to exact power inputs; its proof is not silently a rounded mixed-branch theorem.
Proof sketch or proof idea
Find the rounded size at every level
Proof
(Rounded sizes and the level sum)
For a positive integer b and real x, repeated division satisfies
An integer j is at least the left expression exactly when , equivalently , proving the identity. Induction shows that the size at level j is .
The first size-one level satisfies , giving . Before that level the ratio exceeds one, so
There are exactly nodes at that level because every internal node makes a calls and all have the same size. Their combined toll is bounded above and below by fixed positive multiples of . These inequalities remain valid when d is zero.
Expanding the recurrence to its actual leaves therefore gives
Both sides include the positive base cost. At n one the sum is empty and the leaf term is the base; no internal toll needs to be assigned there.
Evaluate the sum and retain the leaves
Proof
(Geometric regimes and the leaves)
Put . If q is less than one, its partial geometric sums are uniformly bounded above and are at least one for n greater than one. Also , and because L differs from by less than one. Thus the root-scale toll controls the answer.
If q equals one, every internal level contributes order . There are L such levels, and the leaf contribution is order . The total is , producing the stated boundary form. At a one and d zero there is one node per level, each with positive constant toll, so the logarithm is essential.
If q exceeds one, the geometric sum has order for positive L. Its toll contribution is order , while the leaf term has exactly that same order. Thus leaf-scale growth dominates. In this regime the leaves are therefore not a lower-order correction: they have the same order as the internal levels.
Proof X-ray
The competition is between branching and shrinking, not the root toll alone
At each level, branching multiplies the node count by a while size reduction divides each polynomial toll by b to the d. Their ratio determines whether successive levels shrink, stay comparable or grow. Positive base costs keep the last level visible even when logarithmic tolls later decay rapidly.
Floor sizes admit equally direct comparisons
Proof
(Floor sizes and the same comparison)
The corresponding identity for floors is , since the integer interval defining a floor has the same quotient endpoints under integer division. Thus .
The first base level has size below b and at least one, giving . At each internal level, , so
The lower comparison follows from x minus one being at least x divided by two for x at least two. Therefore each level has the same fixed-factor toll comparison as before. The finitely many positive base values have positive minimum and finite maximum, so all leaves again cost order together. Reusing the geometric cases proves the floor theorem without comparing T at different inputs by an unproved monotonicity assumption.
An upper recurrence is not automatically a two-sided runtime estimate
The positive lower toll is what proves the lower half of each conclusion. If a program supplies only an upper bound on its local work, expanding the same tree proves an upper bound, but does not create missing work. For example, a single ceiling-halving call with unit toll has one unit of cost per level and logarithmic total. Changing the toll to the input size gives linear total. Both tolls are bounded above by a constant times the input size, yet their totals have different orders.
The number of actual recursive calls matters too. An implementation that detects a zero operand may skip a branch counted by a three-child mathematical recurrence. The full-tree calculation still bounds it above, while a matching lower bound would need an input family that prevents those shortcuts. Likewise, separately maximizing the toll and each child's cost does not prove that one input realizes all those maxima simultaneously.
Therefore first declare whether a recurrence is an exact work identity, a proved worst-case upper inequality, or a two-sided model with realizable lower work. The theorems here concern the stated positive identities. Their upper-bound parts remain useful for code with less work, but a assertion about that code needs the corresponding lower argument. This distinction also explains why an algorithm's optimization can improve some executions without contradicting the mathematical recursion-tree upper bound.
Critical logarithms reduce to power sums in the depth
Proof
(Critical logarithms as power sums)
For exact n equal to , a level-j subproblem has size . In the critical case , its combined toll at that level is order
Fixed b and fixed r make the logarithm-base factor a constant. Write h equal to L minus j and sum:
For r greater than minus one, elementary integral comparison, or dyadic blocks together with the last half of the sum, gives order . This includes negative r in that range: each term in the last half is within a fixed factor of , yielding the lower bound, and integrating the decreasing power yields the upper bound. For nonnegative r use the corresponding increasing-function comparisons.
At r minus one the sum is harmonic, between and . For r below minus one, the positive series is bounded by one plus its convergent improper integral, and bounded below by its first term. The retained leaf term then has the same constant normalized order. Substituting L proportional to log n proves all three thresholds.
These integral comparisons concern a positive scalar series; they do not assume the original unknown T is monotone. The distinction allows exact integer recursion to remain explicit throughout the earlier theorems.
Worked examples
Worked example 3.2.6
(Ceiling boundaries change an exact answer without changing its order)
Take and . At n eight the depth is three, giving eight leaves and seven internal nodes, so T is fifteen. At n nine the depth is four, giving sixteen leaves and fifteen internal nodes, so T is thirty-one.
The recurrence is in the leaf-dominated regime with p one and d zero, so both answers fit linear asymptotic growth. Replacing the rounded sizes by exact halves would have missed the exact jump and its valid stopping level.
Worked example 3.2.7
(A root-dominated recurrence can still have several full levels)
Let and . At n seven, the first child size is three and its child size one. Total work is root toll seven, next-level toll , and four unit leaves, giving seventeen.
Here , so the general order is linear. Root-dominated describes the summed scale, not the assertion that all nonroot work literally vanishes.
Worked example 3.2.8
(One critical logarithm produces two logarithms in the total)
On powers of two, take base one and . Dividing the level sum by n gives one plus the sum of integers one through L. At n eight, L is three and T is .
The theorem gives . With toll n instead, the normalized sum would be one plus L. The toll's logarithm changes every level's contribution and must be included before applying the critical case.
Concept lensAnalytic
A recursion tree is a sum indexed by scale
Exact rounding identifies which scales actually appear. Polynomial tolls create a geometric progression across those scales, while critical logarithmic tolls create a power sum in the remaining depth. The proof is a controlled finite sum with a separately charged boundary, not a substitution of fractional input sizes into an undefined function.
Common mistakes
Counterexample mode
A ceiling recurrence needs a positive-size base case
If one declared only size zero a base and recursively used at every positive n, then size one would call itself. Its equation would be , which has no finite nonnegative work solution. Rounding and termination hypotheses must be specified before any master estimate is applied.
Common mistake
(Charging only the internal tolls)
Summing the tolls of the internal nodes and stopping there loses the leaves, each of which costs a base value. Take and at . The internal tolls total , but ; with this is , not . Charge the leaves explicitly, as the level sum above does.
Common mistake
(Keeping the boundary form for a logarithmic toll)
In the critical case with a logarithm in the toll, it is tempting to keep the shape or to multiply by a single extra logarithm. On powers of two take and . The level sum gives , so is unbounded: it equals at and at . The correct order is , which is the critical-logarithm theorem with .
Do not use a monotonicity sandwich without proving monotonicity, or transfer the exact-power logarithmic theorem to arbitrary unequal subproblems. Negative overhead cancellation, data-dependent branching and large-integer arithmetic require their own model and bounds.
Summary
Repeated integer division gives exact ceiling/floor sizes and stopping depths. Level comparisons reduce polynomial tolls to a geometric sum with positive leaves, while critical logarithms reduce to depth power sums. This proves precise asymptotic regimes without hiding rounding, base cases or the cost model.
Exercises
Quick check
(Classify , with a positive unit-size base. State why the theorem does not by itself identify an implementation's bit cost unless its toll was measured in bits.)
Compare three with two to the first power.
Solution · Branching produces the multiplication exponent
Here p is and , so the bound is . This is a statement about the declared work function. If g counts word operations on long integers, a separate bit-cost analysis is still required; the recurrence theorem does not turn those operations into unit bit work.
Quick check
(On powers of two, find the order of a recurrence with two half-size calls and toll . Keep a positive base at size one.)
The normalized depth sum is harmonic.
Solution · The reciprocal logarithm gives a log-log factor
At n equal to , every level contributes n divided by its remaining depth, up to the fixed logarithm base. Thus T divided by n has order as L tends to infinity. The result is , with the finitely many smallest powers and the positive base handled separately.
Quick check
(For the floor recurrence with , , base values one at sizes one and two, and toll , compute exactly.)
The first rounded child is already a base size.
Solution · One expansion gives ten
Floor division sends eight to two. Therefore . The depth formula gives , in agreement. Using a ceiling would send eight to three and expand again, producing a different exact recurrence even though the corresponding large-input order is still linear.