A recurrence describes a particular algorithm under a particular cost model; it is not determined merely by the fact that the program is recursive. Here array indexing, fixed-width arithmetic and comparison each cost constant time. We count the work on a given input and use a worst-case bound when input values can change control flow.
Definition 2.4.1
(Recurrence for a cost model)
A recurrence for an algorithm under a stated cost model is an equation that gives the cost on an input of size as the work the call does itself, excluding its recursive calls, plus the costs of the recursive calls it makes. It is derived from the code and is specific to the model.
One recursive branch, then a loop
Consider F(n) for positive integer n:
F(n):
if n <= 1: return
for i = 1 to n: do one unit of work
F(floor(n/2))
Theorem 2.4.2
(Work and stack of the halving recursion)
Let run a loop of iterations and then call itself on , with returning at once for . For its total work satisfies , so , and the call stack holds at most frames. The same holds when the loop runs after the recursive call.
Proof
(A geometric series of different loop lengths)
For powers of two, the loop lengths are n, n/2, n/4, ..., 2. Their sum is less than 2n, and the first loop alone costs n, so T(n)=Theta(n). The number of calls is Theta(log n), but each call does different work. Multiplying n by the number of calls counts every loop as if it were the largest one.
The argument does not depend on n being a power of two: repeated floors only reduce loop lengths, so their sum is at most 2n, while the first loop still gives a linear lower bound for n>1. The call stack has Theta(log n) frames; the time bound does not make the space bound linear.
Counterexample mode
Loop length times number of calls overcounts
A tempting bound multiplies the largest loop length by the number of calls and concludes . For the loops have lengths , so the exact total is , and makes 11 calls, of which 10 run a loop. The product overcounts by a factor of about 5. For the exact total is , so and the claim is false. The correct count adds the different loop lengths, a geometric series.
Worked example 2.4.3
(Counting F exactly for n = 16, 10 and 1)
For the loops have lengths , and returns at once: the total is , with 5 calls. For the arguments are : the loops give , which lies between and , with 4 calls. For the function returns immediately, so the work is and there is one call; the bound is stated only for .
Concept lensCombinatorial
Binary digits give the exact cost
The loop lengths are , which is with its last binary digits dropped. A digit worth contributes to for , hence to the sum over . Summing over digits gives , where is the number of ones in the binary expansion of . The call with argument runs no loop, so for . For this is , for it is , and for it is .
Two branches do not necessarily mean quadratic time
Merge sort on an array of length n makes two calls on halves and then performs linear work to merge the sorted halves into an auxiliary array. For n=2^k, its recurrence is
where c,d>0 represent constant costs in an idealized implementation. At depth j, there are 2^j subproblems of size n/2^j; their total merge work is cn. There are log_2 n internal levels, plus n constant-cost leaves. Thus T(n)=cn log_2 n+dn=Theta(n log n) in this model. For arbitrary n, splitting into floor and ceiling halves preserves the same asymptotic bound. An actual merge may perform different numbers of comparisons on different inputs, but a conventional merge that copies all elements still does linear work at each internal node.
Theorem 2.4.4
(Closed form of the merge sort recurrence)
For , the solution of and is . Hence for constants .
Proof
(Induction on k)
For the formula gives . Assume it for . Then . Since , this equals , which is the formula for .
For arbitrary , with floor and ceiling halves, the same asymptotic bound holds; this note does not prove that case.
Worked example 2.4.5
(Merge sort recurrence for n = 8 with c = d = 1)
With : , , , . The formula gives . As levels: three merge levels cost each, which is , and the 8 leaves cost each, which is . The same check at gives and at gives .
The number of recursive calls and the work per call must both be counted. 2T(n/2) means the two child costs are added, not multiplied. The +cn is work outside the recursive calls and is charged once at each node.
Overlapping subproblems: a different tree
Define W(0)=0, W(1)=1 and W(n)=W(n-1)+W(n-2) for n>=2. A direct recursive implementation calculates the two terms independently. For example, calculating W(5) calls W(4) and W(3), while W(4) itself calls W(3) again. Equal argument values are separate calls unless the program explicitly stores results.
Let C(n) count calls, including the initial call. Then C(0)=C(1)=1 and
Because every non-base call creates exactly two children, this call tree is full. It has W(n+1) leaves, hence C(n)=2W(n+1)-1. The leaf formula follows by induction from the same recurrence and base cases. Thus the naive algorithm makes exponentially many calls: for n>=2, C(n)>=2C(n-2), while C(n)<=2C(n-1)+1 gives an exponential upper bound. These inequalities are sufficient to show exponential growth without needing an exact closed form.
Theorem 2.4.6
(Call count of the naive Fibonacci recursion)
Let be the number of calls, with and for . Then for every , and , so the number of calls grows exponentially.
Proof
(Two inductions)
For the formula: and . If it holds for and , then . For the bound: , since is nondecreasing. With , induction gives .
Proof X-ray
How the two inductions use the recurrence
The formula needs two base cases, because depends on both and ; the check of and is what lets the step start at . The in the recurrence cancels against the in the formula: . The key move in the bound is to compare with instead of solving the recurrence. It needs , which holds because every gives . The comparison discards part of the growth, so it yields , a valid but weaker bound. The induction runs in steps of two, and starts both parities.
Worked example 2.4.7
(Call counts for n = 5 and n = 6, and the smallest cases)
The call counts from the recurrence are 1, 1, 3, 5, 9, 15 for n=0,...,5. A bottom-up method instead sets the two base values and computes successively W(2)=1, W(3)=2, W(4)=3, W(5)=5. It performs n-1 additions for n>=2 and keeps just two previous values if no later reconstruction is needed. This is Theta(n) time and Theta(1) stored values in the unit-cost model. Exact integers grow with n, so arbitrary-precision bit-operation cost and storage in bits are larger than this simplified count.
For : , since ; bottom-up uses additions. For or there is one call, the recursion stops at once, and bottom-up uses no addition.
Memoization is a top-down alternative: store each computed W(k) and return the stored value on subsequent requests. A separate marker is needed to distinguish “not computed” from a computed value of zero. Each argument 0,...,n is computed at most once, yielding O(n) unit-cost operations and O(n) storage, including the recursive stack and table.
Common mistake
(Reading the stack depth as the time)
The number of live frames is the depth of the recursion, not the amount of work. has at most about live frames but takes time. Confusing the two gives either time or stack space.
Common mistake
(Treating equal arguments as one call)
In the naive recursion, is called once under and again under . Unless results are stored, each occurrence is a separate call, so makes calls, not the 6 distinct arguments . Counting distinct arguments describes memoization, not the naive program.
Solved practice: derive, do not guess
Quick check
(For positive integer n, the following code recursively halves n and, after returning, runs an n-iteration loop. What are its time and auxiliary stack bounds?)
G(n):
if n <= 1: return
G(floor(n/2))
for i = 1 to n: do one unit of work
Compare the loop sizes with those of .
Solution · Answer
The order of the recursive call and the loop has changed, but the loop sizes remain n, floor(n/2), floor(n/4), .... Their sum is Theta(n). At maximum depth there are Theta(log n) live calls, so the stack uses Theta(log n) frames. The order affects when work is done and can affect outputs for stateful code, but it does not change this operation count under the stated assumptions.
Quick check
(How many calls does the naive recursion make to compute ?)
Use with the known values up to .
Solution · Answer
, which agrees with .
Quick check
(A function makes one recursive call on and does a constant amount of other work. What are its time and stack bounds?)
Write the recurrence first.
Solution · Answer
The recurrence is with a constant base, so . The recursion is calls deep, so the stack uses frames, unlike the halving function .