10. Recurrences, Generating Functions and Algorithm Analysis

Introduction and Context

Many computational processes are defined in terms of smaller instances of the same process. A sorting algorithm may divide a problem into subproblems; a dynamic-programming algorithm may compute a value from earlier values; a data structure may grow through repeated operations. Such processes are naturally described by recurrence relations. Recurrences provide a mathematical language for expressing running time, memory consumption, combinatorial quantities, and recursively defined objects.

Generating functions offer a complementary method. Instead of studying a sequence term by term, they encode the entire sequence as a formal power series. This makes it possible to derive closed forms, solve recurrences, count structures, and analyze discrete systems. Once a recurrence has been solved, asymptotic notation allows the dominant growth behaviour to be compared independently of machine, programming language, and implementation details.

Algorithm analysis combines these ideas with models of time, space, amortized cost, and probability. A postgraduate computer science student must therefore understand not only how to calculate a bound, but also what the bound means, what assumptions support it, and when one analytical model is more appropriate than another.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Formulate recurrence relations from recursive algorithms and discrete processes.

2. Solve linear and divide-and-conquer recurrences using substitution, iteration, characteristic equations, recursion trees, and the Master Theorem.

3. Use ordinary generating functions to solve recurrences and derive combinatorial identities.

4. Distinguish exact, asymptotic, worst-case, average-case, amortized, and probabilistic bounds.

5. Apply Big-O, Big-Ω, Big-Θ, little-o, and little-ω notation rigorously.

6. Analyse time and space complexity in iterative, recursive, randomized, and data-structure algorithms.

7. Use aggregate, accounting, and potential methods for amortized analysis.

8. Recognize modelling assumptions, analytical errors, and ethical implications of performance claims.

Recurrences as Models of Computation

A recurrence relation defines a sequence by relating one or more terms to earlier terms. For example,

a_n=a_{n-1}+3, \qquad a_0=2

specifies every term after the initial value. The recurrence is incomplete without its base case or initial condition. In algorithm analysis, a recurrence commonly has the form

T(n)=T(n-1)+c,

where T(n) is the cost on an input of size n and c is the work performed outside the recursive call.

A recurrence may be linear if the unknown sequence occurs only to the first power and is not multiplied by another unknown term. It is homogeneous when no independent forcing term occurs, as in a_n=3a_{n-1}; it is non-homogeneous when a term such as n, 2^n, or 1 is added. A recurrence is constant-coefficient when its coefficients do not depend on n. These distinctions determine which solution methods are convenient.

Iteration and telescoping

Consider

T(n)=T(n-1)+n, \qquad T(1)=1.

Repeated substitution gives

T(n)=T(1)+2+3+\cdots+n.

Since the sum is n(n+1)/2-1, T(n)=Θ(n^2). This method, called iteration or unrolling, is especially useful when each expansion reveals a recognizable sum or product.

For a multiplicative recurrence such as

T(n)=2T(n-1), \qquad T(0)=1,

unrolling gives T(n)=2^n. The same approach applied to T(n)=T(n-1)+1 produces T(n)=T(0)+n=Θ(n).

Linear recurrences and characteristic roots

For a homogeneous recurrence

a_n=c_1a_{n-1}+c_2a_{n-2},

assume a solution of the form a_n=r^n. Substitution produces the characteristic equation

r^2-c_1r-c_2=0.

If the roots r_1 and r_2 are distinct, the general solution is a_n=A r_1^n+B r_2^n, where A and B are determined by the initial conditions. If a root r has multiplicity m, the corresponding terms are r^n, nr^n, ..., n^{m-1}r^n.

For the Fibonacci recurrence F_n=F_{n-1}+F_{n-2}, the characteristic equation is r^2-r-1=0. Its roots are φ=(1+√5)/2 and ψ=(1-√5)/2. Consequently, F_n=(φ^n-ψ^n)/√5. Since |ψ|<1, F_n=Θ(φ^n).

A non-homogeneous recurrence can often be solved as the sum of a complementary solution for the homogeneous part and a particular solution for the forcing term. For instance, a particular solution for a polynomial forcing term may be chosen as a polynomial of the same degree, subject to modification when it duplicates a characteristic root.

Divide-and-Conquer Recurrences

A divide-and-conquer algorithm divides an input into subproblems, solves them recursively, and combines their results. A common model is

T(n)=aT(n/b)+f(n),

where a is the number of subproblems, each of size n/b, and f(n) is the non-recursive work.

A recursion tree visualizes the cost at each level. For example, merge sort satisfies

T(n)=2T(n/2)+Θ(n).

At every level, the total merging work is Θ(n), and there are log_2 n levels. Therefore T(n)=Θ(n log n).

The Master Theorem

For T(n)=aT(n/b)+f(n), with a≥1 and b>1, compare f(n) with n^{log_b a}.

• If f(n)=O(n^{log_b a-ε}) for some ε>0, then T(n)=Θ(n^{log_b a}).
• If f(n)=Θ(n^{log_b a} log^k n) for k≥0, then T(n)=Θ(n^{log_b a} log^{k+1} n).
• If f(n)=Ω(n^{log_b a+ε}) for some ε>0 and a regularity condition holds, then T(n)=Θ(f(n)).

For T(n)=3T(n/2)+n, n^{log_2 3} grows faster than n, so the first case applies: T(n)=Θ(n^{log_2 3}). For T(n)=2T(n/2)+n^2, the third case applies, giving Θ(n^2). The theorem does not apply mechanically to every recurrence. Unequal subproblem sizes, non-polynomial irregularities, and missing regularity conditions may require recursion trees, substitution, or more general methods such as the Akra–Bazzi theorem.

Substitution and proof of bounds

The substitution method consists of guessing a bound and proving it by induction. Suppose T(n)=2T(⌊n/2⌋)+n. A suitable guess is T(n)=O(n log n). Substituting the inductive hypothesis gives

T(n)≤2c(n/2)log(n/2)+n = cn log n-cn+n.

For sufficiently large c, the negative term absorbs the additive n, proving the upper bound. A separate lower-bound argument establishes Θ(n log n). This distinction matters: showing O(n log n) alone does not establish tightness.

Generating Functions

For a sequence a_0,a_1,a_2,..., its ordinary generating function is the formal power series

A(x)=Σ_{n≥0}a_nx^n.

The word “formal” emphasizes that algebraic manipulation is primary; convergence may be irrelevant. Generating functions transform shifts and weighted sums into algebraic expressions. If A(x)=Σa_nx^n, then

Σ_{n≥1}a_{n-1}x^n=xA(x),

and, when a_0 is separated,

Σ_{n≥1}a_nx^n=A(x)-a_0.

Solving a recurrence with a generating function

Let a_n=a_{n-1}+1 with a_0=0. Define A(x)=Σ_{n≥0}a_nx^n. Multiplying the recurrence by x^n and summing for n≥1 gives

A(x)=xA(x)+Σ_{n≥1}x^n.

Since Σ_{n≥1}x^n=x/(1-x),

A(x)=xA(x)+x/(1-x),

so A(x)=x/(1-x)^2. The coefficient of x^n in this expression is n, hence a_n=n.

For Fibonacci numbers, F_0=0, F_1=1, and F_n=F_{n-1}+F_{n-2}. The generating function is

F(x)=x/(1-x-x^2).

The denominator reflects the recurrence, while its roots determine the exponential growth. Partial fractions can then recover the closed form.

Counting through generating functions

Generating functions are also used to count selections. Suppose a system may contain any number of components of types A and B, where each component contributes one unit of size. The generating function for each unrestricted type is 1+x+x^2+...=1/(1-x). For two types, the product is 1/(1-x)^2, and the coefficient of x^n counts the number of configurations of total size n.

More constrained systems use factors such as 1+x for a type that may occur at most once, or 1+x^2+x^4+... for an even number of units. Products combine independent choices; coefficient extraction enforces a total-size condition. In algorithmics, this supports analyses of paths, partitions, occupancy models, hashing patterns, and dynamic-programming state counts.

Asymptotic Notation and Growth Comparison

Asymptotic notation describes growth for sufficiently large input sizes. For nonnegative functions f and g,

• f(n)=O(g(n)) if there are constants c>0 and n_0 such that f(n)≤cg(n) for all n≥n_0.
• f(n)=Ω(g(n)) if there are constants c>0 and n_0 such that f(n)≥cg(n) for all n≥n_0.
• f(n)=Θ(g(n)) if both f(n)=O(g(n)) and f(n)=Ω(g(n)).
• f(n)=o(g(n)) if f(n)/g(n)→0.
• f(n)=ω(g(n)) if f(n)/g(n)→∞.

Thus 3n^2+7n+4 is Θ(n^2), and n log n is o(n^{1+ε}) for every fixed ε>0. Constants and lower-order terms disappear in asymptotic classification, but they may matter greatly for small or moderate inputs. It is also important to distinguish an upper bound from a tight bound. An algorithm running in Θ(n) is certainly O(n^2), but O(n^2) communicates less useful information.

Useful growth ordering is

1 << log n << n^α << n << n log n << n^2 << n^k << c^n << n!

for fixed α between 0 and 1, fixed k>1, and c>1. The ordering is asymptotic rather than absolute for every small n.

Analysing Time and Space

Running-time analysis begins with a cost model. In a unit-cost RAM model, arithmetic on a machine-word integer, memory access, and comparison may each be treated as constant time. This model is reasonable when values fit within fixed-size words. If integers grow with n, bit complexity must be considered: adding two L-bit integers costs more than adding two constant-size words.

The analysis should identify the input-size measure. For a graph, n may denote vertices and m edges; for a number, n may denote its numerical value or its binary encoding length log n. Confusing these measures can change a polynomial bound into an exponential one.

Space complexity includes input storage when using an inclusive convention, or only auxiliary storage under an exclusive convention. Recursion depth, call-stack frames, temporary arrays, caches, and output space should be stated clearly. An algorithm may use Θ(n) time and Θ(log n) auxiliary space, as in some divide-and-conquer procedures.

Worst-case complexity bounds the most expensive input of size n. Best-case complexity concerns the least expensive input and is often less useful operationally. Average-case analysis requires a probability distribution over inputs; without that distribution, the phrase “average time” is incomplete. Expected running time may instead refer to randomness internal to an algorithm, conditional on a fixed input.

Amortized and Probabilistic Analysis

Amortized analysis studies the average cost per operation over a sequence, without assuming a probability distribution. It provides a deterministic bound on total cost. Three standard approaches are used.

The aggregate method bounds the total cost of a sequence of n operations and divides by n. For a dynamic array that doubles when full, n insertions cause at most O(n) element moves in total, because the copied capacities form a geometric series. Thus the amortized insertion cost is O(1), even though an individual expansion costs Θ(n).

The accounting method assigns an amortized charge to each operation. Ordinary insertions may be charged three units: one pays for the insertion and two are saved as credits on the element. When resizing occurs, saved credits pay for copying. The charges must never create negative credit.

The potential method defines a nonnegative potential Φ(D) for data-structure state D. The amortized cost of operation i is

ĉ_i = c_i + Φ(D_i)-Φ(D_{i-1}),

where c_i is actual cost. Summing these costs telescopes. A suitable potential for a doubling array increases with the number of stored elements beyond the previous capacity and pays for future copying.

Probabilistic analysis uses random variables and expectations. For randomized quicksort with a uniformly random pivot, the expected running time is Θ(n log n), although the worst case remains Θ(n^2). The expected bound depends on the random-pivot assumption and is not identical to an average-case bound over inputs. High-probability bounds are stronger statements: they assert that a specified bound fails with only a small probability. Concentration inequalities such as Markov’s, Chebyshev’s, or Chernoff bounds may be used when appropriate.

An Illustrative Case Study: Selecting an Algorithm for Large-Scale Search

Background

A fictional online research repository must support search over a collection of records whose number grows from thousands to tens of millions. The engineering team considers linear scanning, binary search over sorted identifiers, and hash-based indexing.

Situation and problem

A linear scan requires Θ(n) comparisons per query. This may be acceptable for small collections but becomes expensive as n grows. Binary search requires sorted data and supports Θ(log n) query time, while maintaining the index may require updates and storage. Hash indexing offers expected Θ(1) lookup under suitable assumptions but can degrade under collisions or adversarial input.

Analysis

The first step is to define the workload: query frequency, insertion frequency, acceptable latency, memory budget, and whether exact or approximate results are required. If the collection is static and identifiers are ordered, sorting costs Θ(n log n) once and binary search gives predictable logarithmic queries. If queries dominate updates and identifiers are exact keys, a hash table may minimize expected lookup time. If worst-case guarantees are essential, balanced search trees provide Θ(log n) search and update bounds.

The team also analyses space. A sorted array has low overhead and good cache locality. A hash table typically needs unused capacity to maintain a low load factor. A tree uses additional pointers and allocation overhead. These constants do not alter asymptotic classes but can determine the practical winner.

Approach and outcome

The repository adopts a sorted, compact index for archival data and a hash-based front index for frequently accessed recent records. Periodic rebuilding combines the two. Monitoring measures actual latency, collision behaviour, memory consumption, and rebuild cost rather than reporting only a theoretical lookup class.

Learning points

The case illustrates that asymptotic analysis supports, but does not replace, engineering judgment. Input assumptions, update patterns, memory hierarchy, adversarial risks, and service-level objectives must accompany a complexity claim. A statement such as “constant-time lookup” should be qualified as expected, amortized, or worst-case, and should identify the assumptions under which it holds.

Common Errors, Limitations, and Professional Considerations

A frequent error is dropping terms before establishing whether they are positive and whether n is sufficiently large. Another is applying the Master Theorem to a recurrence outside its form. Floors and ceilings usually do not affect a Θ bound, but they may matter in exact derivations or irregular recurrences. A further error is confusing recursion depth with total work: a binary recursive procedure can have logarithmic depth but linear or superlinear total cost.

Empirical benchmarking is valuable but cannot prove an asymptotic bound for all inputs. Conversely, a formal bound may hide constants, memory locality, parallelism, vectorization, communication costs, or input distributions that dominate practice. Distributed algorithms require analysis of message complexity, synchronization, and span in addition to local work. Modern systems may also require energy and carbon-aware analysis.

Performance claims have professional and ethical dimensions. Reporting only favourable workloads can mislead users; omitting worst-case behaviour can create safety or security risks. Hashing, randomized algorithms, and machine-learning systems may be vulnerable to adversarial inputs or distribution shift. Reproducible experiments should document hardware, software, data, random seeds, and measurement procedures. Where algorithmic performance affects access to services, analysts should also examine whether optimization sacrifices fairness, privacy, or reliability.

Contemporary Directions

Recurrence-based analysis remains central in parallel algorithms, cache-oblivious algorithms, divide-and-conquer numerical methods, and recursive data processing. Generating functions connect classical discrete mathematics with symbolic computation and analytic combinatorics. Automated theorem provers and computer algebra systems can now manipulate recurrences, search for invariants, and verify inductive bounds, although their results still require interpretation.

For parallel computation, work measures total operations while span measures the length of the critical path. A recurrence can describe both, and parallelism is often estimated as work divided by span. In probabilistic and online algorithms, expected and high-probability guarantees are increasingly combined with robustness analysis. In machine-learning systems, asymptotic complexity is supplemented by data-movement cost, accelerator utilization, training energy, and inference latency.

Best Practices for Algorithm Analysis

1. Define the input-size parameter and computational model before counting operations.

2. State base cases and boundary conditions explicitly when writing a recurrence.

3. Identify whether a bound is exact, upper, lower, tight, expected, amortized, or high probability.

4. Use a recurrence-solving method that matches the recurrence rather than applying a theorem mechanically.

5. Separate preprocessing, query, update, output, and auxiliary-space costs.

6. Check a guessed bound by substitution or induction.

7. Report assumptions about input distributions, randomization, word size, and adversarial behaviour.

8. Combine asymptotic reasoning with experiments and, where relevant, energy, communication, and security analysis.

Chapter Summary

Recurrences model recursive algorithms and discrete processes. They can be solved by iteration, telescoping, characteristic equations, substitution, recursion trees, the Master Theorem, and more general techniques. Generating functions encode sequences as formal power series and convert recurrence manipulation into algebra, supporting both closed-form derivation and combinatorial counting.

Asymptotic notation distinguishes growth rates and expresses upper, lower, and tight bounds. Meaningful algorithm analysis requires an explicit input-size measure and cost model, together with separate consideration of time, space, preprocessing, and output. Worst-case, average-case, expected, amortized, and high-probability statements have different meanings. Amortized analysis uses aggregate, accounting, and potential methods, while probabilistic analysis uses random variables and expectations. Finally, theoretical bounds must be interpreted alongside constants, hardware, workloads, security, fairness, reproducibility, and practical system objectives.

Key Terms

Recurrence relation: An equation defining a sequence or cost in terms of earlier values.

Base case: An initial condition that anchors a recurrence or recursive computation.

Homogeneous recurrence: A recurrence with no independent forcing term.

Characteristic equation: An algebraic equation used to solve constant-coefficient linear recurrences.

Divide and conquer: A method that divides a problem, recursively solves subproblems, and combines results.

Recursion tree: A diagram showing subproblem costs across recursive levels.

Master Theorem: A theorem for bounding recurrences of the form T(n)=aT(n/b)+f(n).

Generating function: A formal power series whose coefficients represent a sequence.

Coefficient extraction: Determining a sequence value from the corresponding generating function.

Asymptotic notation: Mathematical notation describing growth for sufficiently large inputs.

Big-O: An asymptotic upper bound.

Big-Ω: An asymptotic lower bound.

Big-Θ: A tight asymptotic bound.

Amortized analysis: Analysis of average cost over a sequence without probabilistic assumptions.

Potential method: An amortized method using stored abstract potential to pay future costs.

Expected running time: Average cost with respect to an algorithm’s internal randomness or a specified distribution.

High-probability bound: A performance bound that fails only with a small specified probability.

Bit complexity: Cost measured in operations on individual bits or bit-length-dependent integers.

Span: The length of the critical path in a parallel computation.

Review Questions

Short Answer Questions

1. Why must a recurrence relation include a base case?

2. Distinguish Big-O from Big-Θ notation.

3. What information does a characteristic equation provide?

4. Why can a dynamic-array insertion be amortized O(1) despite occasional Θ(n) resizing?

5. How does expected running time differ from average-case running time?

Long Answer Questions

1. Solve T(n)=2T(n/2)+n using a recursion tree and justify the result.

2. Explain the three cases of the Master Theorem and illustrate each with a recurrence.

3. Derive the generating function for the Fibonacci sequence and explain how its denominator reflects the recurrence.

4. Compare the aggregate, accounting, and potential methods of amortized analysis.

5. Discuss why input-size definition and computational model are essential in time and space analysis.

Analytical / Application Questions

1. A recursive procedure makes four calls on subproblems of size n/2 and performs Θ(n^2) combination work. Determine its asymptotic running time and explain which theorem case applies.

2. An online service uses a hash table and claims “constant-time lookup.” Analyse the assumptions and state what additional information should be reported.

3. Design an analysis plan for choosing between a sorted array, balanced tree, and hash index for a workload with frequent searches and occasional updates. Include time, space, worst-case, and expected considerations.

22. Multiple Choice Questions with Answers

Question 1

What is the tight asymptotic bound for T(n)=2T(n/2)+n?

A. Θ(n)

B. Θ(log n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 2

Which condition is essential for a recurrence to be fully specified?

A. It must contain an exponential term

B. It must include a base case

C. It must be homogeneous

D. It must have equal subproblem sizes

Correct Answer: B. It must include a base case

Question 3

The characteristic equation for a_n=3a_{n-1}-2a_{n-2} is:

A. r²+3r-2=0

B. r²-3r-2=0

C. r²-3r+2=0

D. r²+3r+2=0

Correct Answer: C. r²-3r+2=0

Question 4

What is the ordinary generating function of the sequence a_n=n for n≥0?

A. 1/(1-x)

B. x/(1-x)²

C. x/(1+x)²

D. 1/(1-x²)

Correct Answer: B. x/(1-x)²

Question 5

Which statement about amortized analysis is correct?

A. It always assumes a probability distribution over inputs

B. It bounds only the most expensive single operation

C. It bounds average cost over a sequence without requiring randomness

D. It is identical to average-case analysis

Correct Answer: C. It bounds average cost over a sequence without requiring randomness

Question 6

For T(n)=3T(n/2)+n, which term determines the asymptotic result?

A. The base-case cost only

B. n, because it is the additive term

C. n^{log₂3}, because it dominates n

D. log n, because the recursion depth is logarithmic

Correct Answer: C. n^{log₂3}, because it dominates n

Question 7

A claim that an algorithm is O(n²) establishes which fact?

A. Its running time is exactly n²

B. Its running time is at least proportional to n²

C. Its running time is eventually bounded above by a constant multiple of n²

D. Its running time is independent of input distribution

Correct Answer: C. Its running time is eventually bounded above by a constant multiple of n²

Question 8

Which statement best describes a high-probability performance bound?

A. It is always an exact running time

B. It holds except with a specified small probability

C. It applies only to deterministic algorithms

D. It is the same as a worst-case bound

Correct Answer: B. It holds except with a specified small probability

Question 9

Why might binary search be preferable to hashing even when hashing has expected Θ(1) lookup?

A. Binary search never requires sorted data

B. Binary search offers predictable Θ(log n) worst-case behaviour

C. Hashing always uses more time than binary search

D. Binary search requires no comparisons

Correct Answer: B. Binary search offers predictable Θ(log n) worst-case behaviour

Question 10

In a unit-cost RAM model, which issue may require a different analysis?

A. A fixed-size comparison

B. A constant-depth loop

C. Arithmetic on integers whose bit length grows with n

D. Accessing a fixed machine word

Correct Answer: C. Arithmetic on integers whose bit length grows with n