Sequences, Recurrences and Asymptotic Analysis

Introduction

Many computational processes evolve in stages. The amount of memory used by a program may depend on input size, a divide-and-conquer algorithm may repeatedly split a problem, and a simulation may calculate each state from earlier states. Mathematics for these situations is provided by sequences, series, summations, recurrence relations, and asymptotic analysis.

A sequence is an ordered list of values indexed by integers. A recurrence defines later values using earlier values. Asymptotic notation describes how resource requirements grow as the input becomes large, while deliberately ignoring machine-dependent constants and lower-order terms. These ideas provide the mathematical foundation for algorithm analysis, dynamic programming, data-structure design, numerical computation, and discrete modelling.

Learning Objectives

By the end of this chapter, a student should be able to:

• distinguish sequences, series, finite sums, and infinite series;
• derive and use arithmetic and geometric-sum formulas;
• formulate recurrence relations from algorithms;
• solve recurrences by substitution, iteration, characteristic roots, and generating functions;
• explain the assumptions behind O, Ω, Θ, o, and ω notation;
• analyze common algorithms and compare their scalability;
• identify limitations of asymptotic analysis.

1. Sequences and Series

A sequence is a function from a set of integers, usually the nonnegative integers, to the real or complex numbers. It is written as (a_n)_n≥0 or a₀,a₁,a₂,.... The index n identifies the position, and a_n is the nth term.

A sequence may be specified explicitly, recursively, or by a rule. For example, a_n=3n+1 is explicit, whereas a₀=1, a_n=a_n-1+3 is recursive. In the latter case, the recurrence and initial condition together determine the sequence.

A series is a sum of sequence terms. A finite partial sum is

where S_n is the sum through index n. An infinite series is written ∑_k=0^∞a_k and is defined through the limit of its partial sums, if that limit exists:

An infinite series converges when this limit is finite; otherwise it diverges. A necessary, but not sufficient, condition for convergence is a_n→0. For example, the terms of the harmonic series 1/n approach zero, but ∑_n=1^∞1/n diverges.

Arithmetic sequences and sums

An arithmetic sequence has a constant difference d between consecutive terms:

Here a₀ is the first term when indexing begins at zero, d is the common difference, and n is a nonnegative integer. Its first n+1 terms have sum

The formula follows by writing the sum forwards and backwards and adding corresponding terms. It is valid for every finite arithmetic sequence.

Geometric sequences and sums

A geometric sequence has a constant ratio r between consecutive nonzero terms:

For r≠1,

Equivalently, the numerator and denominator may both be multiplied by −1. If |r|<1, the infinite geometric series converges:

The condition |r|<1 is essential. If |r|≥1 and a₀≠0, the infinite geometric series does not converge.

Common summations

Several sums appear frequently in algorithm analysis:

For fixed integer p≥0, ∑_k=1ⁿ k^p grows on the order of n^p+1. Exact formulas are useful for precise counts; asymptotic forms are usually sufficient for scalability decisions.

2. Recurrence Relations

A recurrence relation specifies a sequence term in terms of earlier terms. The initial conditions supply enough starting values to make the sequence unique. For example,

models a process that performs n additional units of work at stage n.

In algorithm analysis, a recurrence usually describes running time. If an algorithm solves one subproblem of size n−1 and performs n additional operations, its running time may satisfy the recurrence above. If it creates two subproblems of half the size and performs linear combination work, a suitable model is

where c is a positive constant and the floor accounts for integer input sizes. Recurrences are models: they depend on the chosen cost measure, implementation, input representation, and base case.

A recurrence is not complete without initial conditions. For example, T(n)=2T(n−1) has infinitely many solutions until T(0) is specified.

3. Solving Recurrences by Iteration

Iteration, also called expansion or repeated substitution, replaces a recurrence by successively earlier terms.

Worked Example 1: Linear additive recurrence

Solve T(n)=T(n−1)+3n, with T(0)=2.

Expanding gives

T(n)=T(n−2)+3(n−1)+3n,

and after continuing to the base case,

T(n)=T(0)+3∑_k=1ⁿk.

Therefore,

Thus T(n) is quadratic and belongs to Θ(n²). The exact expression is valuable because it verifies the asymptotic conclusion.

Worked Example 2: Divide-and-conquer recurrence

Consider

Assume first that n is a power of two. Expanding j levels produces

because each level contributes total work n. At the base case, choose j=log₂ n. Hence

and therefore T(n)∈Θ(n log n). For arbitrary integer n, floors and ceilings alter constants and lower-order details but not this asymptotic class under the usual bounded-cost assumptions.

4. Substitution and Induction

The substitution method has two stages: guess a bound and prove it, usually by mathematical induction. It is especially useful when an exact solution is unnecessary.

Suppose T(n)=2T(⌊n/2⌋)+n. We guess T(n)≤cn log₂ n for sufficiently large n. Assume the claim holds for smaller inputs. Then

T(n)≤2c⌊n/2⌋log₂⌊n/2⌋+n.

Using ⌊n/2⌋≤n/2 and the fact that the logarithm decreases when its argument is halved,

T(n)≤cn(log₂ n−1)+n = cn log₂ n−(c−1)n.

For c≥1, this is at most cn log₂ n. A finite adjustment of c handles the base cases. The proof establishes an upper bound, not necessarily an exact formula.

A common error is to substitute the guessed bound without checking base cases or the direction of inequalities. Another is to use a bound that is too tight to absorb the nonrecursive work. A strengthened hypothesis, such as T(n)≤cn log n−dn, may be required in difficult proofs.

5. Characteristic Roots

Linear homogeneous recurrences with constant coefficients can often be solved using characteristic equations. Consider

with constants c₁ and c₂. Try a solution x_n=rⁿ. Substitution gives

called the characteristic equation.

If the roots r₁ and r₂ are distinct, the general solution is

where A and B are determined by the two initial conditions. If there is a repeated root r, the solution is

For a recurrence of order m, each distinct root contributes a term involving its power; a root of multiplicity q contributes a polynomial of degree q−1 multiplied by that power.

Worked Example 3: Fibonacci-type recurrence

Let F_n=F_n−1+F_n−2, with F₀=0 and F₁=1. The characteristic equation is

Its roots are φ=(1+√5)/2 and ψ=(1−√5)/2. Solving for the constants gives

Since |ψ|<1 and φ>1, Fibonacci numbers grow as Θ(φⁿ). This does not mean every implementation of Fibonacci takes exponential time: a direct recursive program repeats computations, whereas iterative dynamic programming computes all values through n in Θ(n) time and Θ(1) extra space.

6. Generating Functions

A generating function encodes a sequence as a formal power series. For sequence (a_n), its ordinary generating function is

In combinatorics, this is often manipulated formally, so convergence need not be assumed. Generating functions transform recurrence relations into algebraic equations.

For the Fibonacci sequence, let F(x)=∑_n=0^∞F_nxⁿ. Since F₀=0 and F₁=1, shifting the recurrence gives

and hence

Factoring the denominator or using partial fractions recovers the characteristic-root formula. Generating functions are particularly useful for counting objects, deriving closed forms, and analyzing recurrences whose inhomogeneous terms are difficult to handle directly.

7. Asymptotic Notation

Asymptotic notation describes growth as n→∞. Let f and g be eventually nonnegative functions on positive integers.

• f(n)∈O(g(n)) means there are constants c>0 and n₀ such that 0≤f(n)≤cg(n) for all n≥n₀. It is an asymptotic upper bound.
• f(n)∈Ω(g(n)) means there are constants c>0 and n₀ such that 0≤cg(n)≤f(n) for all n≥n₀. It is an asymptotic lower bound.
• f(n)∈Θ(g(n)) means both bounds hold. Thus f and g have the same asymptotic order.
• f(n)∈o(g(n)) means, informally, f grows strictly more slowly; formally, lim_n→∞f(n)/g(n)=0 when the ratio is defined.
• f(n)∈ω(g(n)) means g(n)∈o(f(n)).

For example, 3n²+7n+4∈Θ(n²). The coefficient 3 and lower-order terms do not affect the growth class. Logarithm bases also differ only by a constant because log_a n=log_b n/log_b a, so Θ(log₂ n)=Θ(ln n).

Asymptotic notation is not a statement about equality for every input. Writing T(n)=O(n²) is common, but the mathematically precise form is T(n)∈O(n²). Also, an algorithm in O(n²) may simultaneously be in O(n³); the tightest useful classification is usually Θ(n²).

Growth-rate hierarchy

For typical positive constants and sufficiently large n,

where 0<a<b and c>1. The symbol ≺ indicates asymptotically smaller growth. This hierarchy explains why an algorithm that is acceptable for small inputs may become unusable at scale.

Algebraic rules

If f∈O(g) and h∈O(k), then f+h∈O(g+k) and fh∈O(gk). For nonnegative terms, a finite sum is dominated by its largest asymptotic term. Thus n²+n log n+5∈Θ(n²). These rules apply to eventual growth and should not be used blindly when cancellation or negative values are significant.

8. Algorithmic Applications

To analyze an algorithm, first define the input-size measure n, select a basic operation or resource, count how often it occurs, and then simplify the resulting function asymptotically. Worst-case, best-case, average-case, and amortized analyses answer different questions.

A loop that doubles a counter each iteration runs Θ(log n) times. Nested loops do not automatically imply Θ(n²): a loop with an inner bound that depends on the outer index may produce a summation such as ∑_i=1ⁿi=Θ(n²), while a halving inner loop may produce Θ(n log n).

Space complexity should distinguish input storage from auxiliary space. An algorithm may have Θ(n) total memory but only Θ(1) auxiliary memory. Likewise, asymptotic time ignores constants, cache effects, parallelism, compiler optimization, and actual input distributions. For practical engineering decisions, both asymptotic growth and measured performance matter.

Applied Case: Choosing a Search Strategy

Background

An online service maintains a sorted collection of n user identifiers and must answer membership queries.

Problem

A sequential scan examines entries from the beginning and may inspect n entries in the worst case, giving Θ(n) time per query. The engineering team considers binary search.

Analysis

Binary search compares the target with the middle entry and discards approximately half the remaining candidates. Its recurrence is

where c and d are positive constants representing comparison and base-case costs. After about log₂ n levels, the search reaches one element, so T(n)∈Θ(log n).

If the collection is stored in an array, binary search also benefits from compact storage and predictable indexing. If identifiers change frequently, maintaining sorted order may impose insertion costs. A hash table can provide expected Θ(1) lookup under suitable assumptions, but it requires additional memory, depends on a good hash function, and has a worst-case Θ(n) lookup under severe collisions.

Outcome

For mostly static sorted data, binary search offers a strong deterministic trade-off. For frequent updates and sufficiently available memory, hashing may be preferable. The correct decision depends on query volume, update frequency, memory constraints, ordering requirements, and worst-case guarantees—not on a single asymptotic label.

Learning points

1. A recurrence exposes the structural reason for logarithmic search time.
2. Expected and worst-case bounds must not be confused.
3. Data representation affects both operation complexity and practical performance.
4. Asymptotic analysis supports design decisions but does not replace benchmarking and system-level evaluation.

Limitations, Best Practices, and Contemporary Relevance

Asymptotic models assume that input size is an appropriate measure and that elementary operations have comparable cost. In modern systems, this may be false: memory hierarchy, network latency, energy consumption, vectorization, accelerators, and parallel execution can dominate. Randomized and machine-learning algorithms also require probabilistic or empirical analyses in addition to deterministic bounds.

Best practice is to state the resource being measured, specify the case being analyzed, declare assumptions about input representation and arithmetic cost, retain floors and ceilings until their effect is understood, and verify results using small instances or independent derivations. In AI and data-intensive systems, recurrence-based scaling estimates help forecast training or inference cost, but responsible deployment also requires attention to energy use, privacy, security, fairness, and reproducibility. Mathematical efficiency does not by itself establish social or ethical acceptability.

Chapter Summary

Sequences represent ordered indexed values, while series sum sequence terms. Arithmetic and geometric formulas provide essential tools for evaluating finite and infinite sums. Recurrence relations model processes whose current cost or value depends on earlier states; they require initial conditions and can be solved by iteration, substitution with induction, characteristic roots, or generating functions. Characteristic roots give closed forms for linear constant-coefficient recurrences, while generating functions convert sequence problems into algebraic ones.

Asymptotic notation formalizes growth: O gives an upper bound, Ω a lower bound, Θ a tight bound, and o and ω strict comparisons. Algorithm analysis uses summations and recurrences to estimate time and space, but practical choices must also consider constants, memory behavior, updates, randomness, hardware, and workload. The central professional skill is to connect a precise mathematical model with clearly stated engineering assumptions.

Key Terms

Sequence: An ordered function whose terms are indexed, usually by nonnegative integers.

Series: A sum of terms from a sequence.

Partial sum: The finite sum of the first specified terms of a series.

Convergence: The property of an infinite series or sequence approaching a finite limit.

Arithmetic sequence: A sequence with a constant difference between consecutive terms.

Geometric sequence: A sequence with a constant ratio between consecutive terms.

Recurrence relation: An equation defining a term using earlier terms.

Initial condition: A starting value or set of values needed to determine a recurrence.

Iteration: Repeated expansion of a recurrence until a base case is reached.

Substitution method: Guessing and inductively proving an asymptotic bound.

Characteristic equation: An algebraic equation whose roots determine solutions of a linear recurrence.

Generating function: A formal power series encoding the terms of a sequence.

Asymptotic analysis: Study of growth as input size tends to infinity.

Big-O: An asymptotic upper bound.

Big-Ω: An asymptotic lower bound.

Big-Θ: An asymptotically tight bound.

Worst-case complexity: Maximum resource use over inputs of a given size.

Amortized analysis: Average cost per operation over a sequence of operations, without requiring probability.

Auxiliary space: Extra memory used beyond the input representation.

Review Questions

Short Answer Questions

1. What is the difference between a sequence and a series?
2. State the convergence condition for an infinite geometric series.
3. Why are initial conditions necessary for a recurrence relation?
4. Define f(n)∈Θ(g(n)).
5. What does a characteristic root represent in a linear recurrence?

Long Answer Questions

1. Derive the finite geometric-sum formula and explain the condition under which the corresponding infinite series converges.
2. Solve T(n)=T(n−1)+n, with T(0)=0, by iteration and classify its growth.
3. Explain the substitution method, including the role of induction and base cases.
4. Derive the closed form of the Fibonacci recurrence using characteristic roots.
5. Compare binary search, sequential search, and hashing in terms of assumptions, time bounds, and practical trade-offs.

Analytical / Application Questions

1. An algorithm satisfies T(n)=3T(⌊n/2⌋)+n. Use iteration to predict its asymptotic growth and justify each level's contribution.
2. A system performs operations with costs 1,2,4,...,2^k until the total cost first exceeds n. Estimate the number of operations and total cost using geometric sums.
3. A database team must choose between a sorted array and a hash table for a workload with frequent queries and occasional updates. Formulate the relevant cost model and recommend a structure under two different workload assumptions.

Multiple Choice Questions with Answers

Question 1

Which condition makes the infinite geometric series ∑_k=0^∞ ar^k converge when a≠0?

A. r=1

B. |r|<1

C. r>1

D. a=0 only

Correct Answer: B. |r|<1

Question 2

What is the exact value of ∑_k=1ⁿ k?

A. n²

B. n(n−1)/2

C. n(n+1)/2

D. 2n+1

Correct Answer: C. n(n+1)/2

Question 3

If T(n)=T(n−1)+3n and T(0)=2, what is T(n)?

A. 2+3n

B. 2+3n(n+1)/2

C. 3n²+2

D. 2·3^n

Correct Answer: B. 2+3n(n+1)/2

Question 4

The recurrence T(n)=2T(n/2)+n has which asymptotic solution under standard divide-and-conquer assumptions?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 5

Which statement correctly defines f(n)∈Θ(g(n))?

A. f is eventually bounded above and below by constant multiples of g

B. f is always exactly equal to g

C. f grows strictly more slowly than g

D. f is bounded above only

Correct Answer: A. f is eventually bounded above and below by constant multiples of g

Question 6

For a repeated characteristic root r in a second-order linear homogeneous recurrence, the general solution has the form:

A. A+B+r^n

B. (A+Bn)r^n

C. Ar^n+B/r^n only

D. A n^r+B

Correct Answer: B. (A+Bn)r^n

Question 7

What is the ordinary generating function of the Fibonacci sequence with F₀=0 and F₁=1?

A. 1/(1−x)

B. x/(1−x)

C. x/(1−x−x²)

D. (1−x−x²)/x

Correct Answer: C. x/(1−x−x²)

Question 8

An algorithm that halves its remaining input at each iteration performs how many iterations asymptotically?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 9

Which statement about Big-O notation is correct?

A. It always gives a tight bound

B. It describes an asymptotic upper bound

C. It applies only to exponential functions

D. It ignores the input size

Correct Answer: B. It describes an asymptotic upper bound

Question 10

A sequential search through an unsorted array has what worst-case time complexity?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: C. Θ(n)