Sequences, Recurrence Relations and Asymptotic Growth

Introduction

Computer applications frequently involve processes that evolve step by step. A program may generate successive approximations, a data structure may grow as records are added, or an algorithm may divide a problem into smaller subproblems. Sequences provide a mathematical model for indexed values, while recurrence relations describe how later values depend on earlier ones. Asymptotic notation then allows us to compare the growth of running time, memory use, or data volume as the input becomes large.

These ideas are central to algorithm analysis. They help a developer decide whether an algorithm will remain practical when an input grows from thousands to millions of elements. They also support analysis of recursive programs, dynamic programming, divide-and-conquer methods, and iterative numerical procedures.

Learning Objectives

After studying this chapter, you should be able to:

1. Define and represent finite and infinite sequences.
2. Distinguish explicit formulas from recurrence definitions.
3. Formulate recurrence relations for recursive processes.
4. Solve common first-order and second-order linear recurrences.
5. Use iteration, characteristic equations, and substitution appropriately.
6. Explain Big-O, Big-Theta, and Big-Omega notation formally and intuitively.
7. Compare algorithmic growth rates and identify scalability implications.
8. Apply recurrence and asymptotic analysis to a realistic computing problem.

1. Sequences as Models of Discrete Change

A sequence is an ordered list of values indexed by integers. It is commonly written as

or as {a_n}, where n belongs to a specified index set, usually the non-negative integers. The value a_n is called the n-th term. The index has no unit unless the application assigns one, such as an iteration number, time period, or input size.

A sequence may be:

• Finite, such as 2,4,6,8, or
• Infinite, such as 1,1/2,1/3,….

An explicit definition gives the term directly in terms of its index. For example,

gives a₀ = 2, a₁ = 5, and a₂ = 8. A recursive definition gives one or more initial values and a rule for obtaining later values from earlier ones. For example,

also generates 2, 5, 8, … .

1.1 Important Types of Sequences

An arithmetic sequence has a constant difference between consecutive terms:

where a₀ is the initial term and d is the common difference. The formula applies when the sequence begins at index 0.

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

where r is the common ratio. If |r| < 1, the terms approach zero; if |r| > 1, their magnitudes grow without bound.

The partial sum of the first n+1 terms is

For a geometric sequence with r ≠ 1,

If |r| < 1, the infinite geometric series converges to

The infinite formula is applicable only when |r| < 1.

2. Recurrence Relations

A recurrence relation defines a sequence by relating a term to preceding terms. A recurrence is complete only when sufficient initial conditions are supplied.

For example,

models a process that performs four additional units of work at each step. The first values are T(0)=3, T(1)=7, and T(2)=11.

The order of a recurrence is the greatest number of previous positions needed. The recurrence a_n = 2a_n−1+1 is first-order, while a_n = a_n−1+a_n−2 is second-order.

A recurrence is linear if each term and previous term occurs only to the first power and is not multiplied by another sequence term. It is homogeneous if there is no separate forcing term. Thus:

• a_n = 3a_n−1 − 2a_n−2 is linear homogeneous.
• a_n = 3a_n−1 + n is linear non-homogeneous.
• a_n = (a_n−1)² is nonlinear.

The order and linearity determine which solution methods are available.

2.1 Modelling Recursive Algorithms

Suppose an algorithm processes an input of size n by making two recursive calls on inputs of size n/2, plus linear work for partitioning and combining. Its running time can be modelled as

where c and d are positive constants. The recurrence is a mathematical abstraction: it counts dominant operations rather than recording every instruction.

For a loop that removes one item at each iteration, a typical recurrence is

For a recursive process that branches into two subproblems of size one less, the recurrence may be

This distinction is important. Similar-looking recursive code can have radically different growth depending on the number and size of subproblems.

3. Solving First-Order Linear Recurrences

Consider the first-order recurrence

where r, c, and A are constants.

3.1 Iteration Method

Repeated substitution gives

For r ≠ 1, the geometric-sum formula gives

An equivalent form is

For the special case r=1,

The formula must be checked against the initial condition and recurrence.

Worked Example 1: A First-Order Recurrence

Solve

Here r=2, c=3, and A=1. Therefore,

The first terms are 1, 5, 13, and 29. The formula produces 4·2⁰−3=1, 4·2¹−3=5, and 4·2²−3=13, confirming the result.

3.2 Equilibrium or Particular Value

For r ≠ 1, a constant equilibrium value [[MATH{p}]] satisfies

so

The general solution can be written as

This form is especially useful for interpreting convergence. If [[MATH{|r|<1]], then rⁿ→0, and the sequence approaches p. If [[MATH{|r|>1]], deviations from equilibrium grow in magnitude. If r<0, the sequence may alternate around its equilibrium.

4. Second-Order Linear Homogeneous Recurrences

A common second-order recurrence is

with initial values a₀ and a₁. To solve it, assume a trial solution a_n = λⁿ. Substitution gives

Dividing by λⁿ⁻² when λ ≠ 0 produces the characteristic equation

4.1 Distinct Real Roots

If the characteristic equation has distinct roots λ₁ and λ₂, then

The constants C₁ and C₂ are found from the two initial conditions.

Worked Example 2: Distinct Roots

Solve

The characteristic equation is

Thus

Using the initial values:

Subtracting twice the first equation from the second gives C₂=1, and hence C₁=1. Therefore,

4.2 Repeated Roots

If the characteristic equation has a repeated root λ, the solution is

The factor n is essential; omitting it generally gives only one independent solution.

4.3 Complex Roots

If roots are complex, they occur in conjugate pairs when the recurrence has real coefficients. The resulting real sequence can be expressed using powers of the root magnitude and sine and cosine terms. In elementary algorithm analysis, the magnitude of the roots is usually more important than the oscillation: the largest magnitude determines the dominant exponential growth.

5. Non-Homogeneous Linear Recurrences

A non-homogeneous recurrence has a forcing term, for example

Its solution has two parts:

The homogeneous part solves the recurrence with f(n)=0. A particular solution is chosen according to the form of f(n). For example, if the forcing term is a constant and 1 is not a characteristic root, a constant trial value may be appropriate. If the trial form duplicates a homogeneous solution, it must be multiplied by a sufficient power of n.

For algorithm analysis, exact constants are often less important than the dominant term. Nevertheless, an exact solution is valuable when validating a model or studying small inputs.

6. Recursion Trees and Divide-and-Conquer Recurrences

A recurrence such as

can be understood through levels of recursive calls. At level 0, the nonrecursive work is cn. At level 1, there are two subproblems, each contributing c(n/2), so the total remains cn. The same is true at every internal level. There are approximately log₂ n levels, so the total internal work is proportional to n log n. The leaves contribute proportional to n when the base-case cost is constant. Consequently,

This reasoning underlies the analysis of merge sort.

By contrast,

has one subproblem per level and therefore has growth Θ(log n). A recurrence of the form

has approximately 2 branches for each decrement and grows exponentially, Θ(2ⁿ).

7. Asymptotic Growth and Algorithm Analysis

Asymptotic analysis studies behaviour as the input size n becomes large. It deliberately ignores machine-dependent constants, lower-order terms, and implementation details that do not change the broad growth class.

7.1 Big-O Notation

A function f(n) is O(g(n)) if there exist constants c>0 and n₀ such that

This means g(n) is an eventual upper bound up to a constant factor. In algorithm analysis, saying an algorithm is O(n²) usually means its running time grows no faster than a constant multiple of n² for sufficiently large inputs.

Big-O is not necessarily a tight description. A linear function is also O(n²), although Θ(n) is more informative.

7.2 Big-Omega Notation

A function f(n) is Ω(g(n)) if there exist constants c>0 and n₀ such that

It is an eventual lower bound up to a constant factor. For example, n²+3n is Ω(n²). In a particular implementation, a lower bound may refer to a guaranteed running time; in complexity theory, it may refer to the minimum resources required by any algorithm in a model.

7.3 Big-Theta Notation

A function f(n) is Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that

Thus Θ(g(n)) is both an upper and a lower bound of the same asymptotic order. For example,

because the quadratic term dominates the linear and constant terms.

7.4 Common Growth Classes

The table describes growth, not exact execution time. Hardware, programming language, memory locality, parallelism, and input distribution also matter.

7.5 Simplifying Asymptotic Expressions

When n tends to infinity, constants and lower-order terms can be removed from a polynomial expression:

For logarithms, the base is irrelevant in asymptotic notation because

and the conversion factor is constant for fixed positive bases a,b ≠ 1. Thus log₂ n and ln n belong to the same asymptotic class.

For products and nested operations, count the dominant contribution carefully. Two consecutive loops of lengths n and n perform Θ(n)+Θ(n)=Θ(n) work, whereas a nested pair performs Θ(n²) work. A loop that doubles its index each iteration has Θ(log n) iterations because after k iterations its index is approximately 2^k.

8. Worked Algorithm Analysis

Consider the following pseudocode:

for i = 1 to n:
    j = 1
    while j ≤ n:
        process(i, j)
        j = 2j

The outer loop executes n times. For each fixed i, the inner loop takes approximately log₂ n iterations, since the values of j are 1, 2, 4, … . Therefore the total running time is

This analysis assumes that process(i,j) takes constant time. If it performs Θ(n) work, the total would instead be Θ(n² log n). The cost of the body must therefore be included in a reliable analysis.

9. Applied Case: Choosing a Search Strategy for a Growing Catalogue

Background

This illustrative case concerns a university library application that searches a catalogue containing records identified by unique numeric keys. The initial catalogue contains 50,000 records, but the institution expects it to grow to 10 million records.

Problem

A sequential search examines records from the beginning until it finds the requested key or reaches the end. In the worst case, it examines all n records, giving Θ(n) time. The development team is considering a sorted array with binary search, which requires the data to be ordered.

Analysis

Binary search compares the target with the middle record and discards half of the remaining records after each comparison. Its recurrence is

where c is the constant cost of one comparison and control step. The number of halvings needed to reduce n to 1 is approximately log₂ n, so binary search has Θ(log n) search time.

For 10 million records, log₂(10,000,000) is approximately 23.25, so at most about 24 halvings are required, ignoring implementation details. Sequential search could require 10 million comparisons in the worst case.

Approach and Outcome

The team chooses binary search for read-heavy catalogue queries and maintains the sorted index whenever records are inserted. The search operation scales much better, but insertion into a contiguous sorted array may require shifting Θ(n) records. If frequent insertion is more important than fast indexed search, a balanced search tree or database index may be preferable.

Learning Points

1. Asymptotic analysis supports decisions about future scale, not just present performance.
2. A fast query operation may impose a maintenance cost elsewhere.
3. The data structure and workload must be analysed together.
4. Big-Theta describes growth, but actual constants and system architecture remain relevant.

10. Limitations, Best Practices and Professional Relevance

Asymptotic notation suppresses constants and lower-order terms. Consequently, an O(n log n) algorithm may be slower than an O(n²) algorithm for small inputs if its constant overhead is high. Best-case, average-case, and worst-case analyses can also differ. A complete performance decision should combine asymptotic reasoning with measurement, memory analysis, workload characteristics, and hardware constraints.

When constructing a recurrence:

• Define precisely what T(n) measures.
• State the base case and the domain of n.
• Identify the number and size of recursive calls.
• Include nonrecursive work at each call.
• Check whether floors and ceilings affect only constants or change the result.
• Verify the result using small values or a second method.

In professional software engineering, performance claims should be reproducible and honest. Developers should not present an upper bound as an exact running time, or confuse an average-case statement with a guarantee. When algorithmic choices affect access to public services, financial decisions, or safety-related systems, scalability and resource assumptions should be documented so that stakeholders can evaluate them.

Contemporary systems also use automated profiling and AI-assisted code tools. Such tools can suggest optimisations, but they do not replace mathematical modelling: generated code may alter data structures, introduce hidden costs, or improve average performance while worsening worst-case behaviour. A sound engineering process combines recurrence analysis, asymptotic reasoning, empirical profiling, testing, and review.

Chapter Summary

Sequences model ordered discrete values. They may be defined explicitly or recursively, and arithmetic and geometric sequences provide fundamental examples. A recurrence relation describes a term through earlier terms and must be accompanied by initial conditions. First-order linear recurrences can often be solved by iteration or equilibrium analysis. Second-order homogeneous recurrences are commonly solved using a characteristic equation; distinct roots, repeated roots, and complex roots require different forms.

Recursive algorithms can be translated into recurrences that expose their computational structure. Recursion trees are useful for understanding divide-and-conquer methods such as merge sort. Big-O gives an asymptotic upper bound, Big-Omega gives a lower bound, and Big-Theta gives a tight asymptotic bound. Growth classes such as logarithmic, linear, linearithmic, quadratic, exponential, and factorial describe increasingly demanding scalability. Good professional analysis combines these abstractions with base cases, assumptions, empirical evidence, memory requirements, and workload characteristics.

Key Terms

Sequence: An ordered list of values indexed by integers.

Term: A particular value in a sequence, such as a_n.

Explicit definition: A formula that gives a term directly from its index.

Recursive definition: A definition using initial values and earlier terms.

Arithmetic sequence: A sequence with a constant consecutive difference.

Geometric sequence: A sequence with a constant consecutive ratio.

Recurrence relation: An equation relating sequence terms at different indices.

Initial condition: A specified starting value needed to determine a recurrence.

Order: The greatest number of previous terms used by a recurrence.

Linear recurrence: A recurrence in which sequence terms occur to the first power and are not multiplied together.

Homogeneous recurrence: A recurrence with no separate forcing term.

Characteristic equation: An auxiliary polynomial used to solve a linear homogeneous recurrence.

Particular solution: One solution of a non-homogeneous recurrence.

Asymptotic analysis: Study of growth as input size becomes large.

Big-O: An eventual asymptotic upper bound.

Big-Omega: An eventual asymptotic lower bound.

Big-Theta: A tight asymptotic bound.

Recursion tree: A representation of subproblem costs across recursive levels.

Dominant term: The term that determines asymptotic growth for large input.

Scalability: The ability of a system or algorithm to remain practical as workload grows.

Review Questions

5 Short Answer Questions

1. What is the difference between an explicit and a recursive sequence definition?
2. Why are initial conditions necessary for a recurrence relation?
3. State the characteristic equation for a_n = p a_n−1 + q a_n−2.
4. What does Θ(g(n)) communicate about a function?
5. Why does repeatedly doubling a loop variable result in logarithmic iteration count?

5 Long Answer Questions

1. Derive the closed form of a_n = r a_n−1+c for r ≠ 1, given a₀=A.
2. Explain how distinct and repeated characteristic roots produce different solutions for second-order recurrences.
3. Compare Big-O, Big-Omega, and Big-Theta using formal inequalities and computing examples.
4. Use a recursion-tree argument to analyse T(n)=2T(n/2)+cn.
5. Discuss why asymptotic analysis should be supplemented by empirical measurement and memory analysis.

3 Analytical / Application Questions

1. A recursive algorithm makes three calls on subproblems of size n/2 and performs Θ(n) additional work. Formulate a recurrence and determine its asymptotic growth.
2. A database search is changed from sequential search to binary search. Analyse the benefits, the required data condition, and a possible cost introduced by maintaining that condition.
3. For a_n = 4a_n−1 − 4a_n−2, with a₀=1 and a₁=4, solve the recurrence and explain how the repeated root affects the growth.

Multiple Choice Questions with Answers

Question 1

Which formula defines an arithmetic sequence with initial term a₀ and common difference d?

A. a_n=a₀rⁿ

B. a_n=a₀+nd

C. a_n=ndⁿ

D. a_n=a₀+n/d

Correct Answer: B. a_n=a₀+nd

Question 2

What additional information is required to determine a recurrence relation uniquely?

A. Only its order

B. Only its largest coefficient

C. Its initial conditions

D. The logarithm base

Correct Answer: C. Its initial conditions

Question 3

The recurrence a_n=2a_n−1+3, a₀=1, has which closed form?

A. 2ⁿ+3

B. 3·2ⁿ−1

C. 4·2ⁿ−3

D. 2n+3

Correct Answer: C. 4·2ⁿ−3

Question 4

What is the characteristic equation of a_n=5a_n−1−6a_n−2?

A. λ²+5λ−6=0

B. λ²−5λ−6=0

C. λ²−5λ+6=0

D. λ²+5λ+6=0

Correct Answer: C. λ²−5λ+6=0

Question 5

If a second-order recurrence has a repeated characteristic root λ, which solution form is appropriate?

A. C₁λⁿ+C₂λⁿ

B. (C₁+C₂n)λⁿ

C. C₁n+C₂λ

D. C₁λ+C₂n²

Correct Answer: B. (C₁+C₂n)λⁿ

Question 6

Which statement is the formal meaning of f(n)=Θ(g(n))?

A. Only an asymptotic upper bound exists

B. Only an asymptotic lower bound exists

C. Both upper and lower constant-factor bounds hold eventually

D. The two functions are exactly equal for every n

Correct Answer: C. Both upper and lower constant-factor bounds hold eventually

Question 7

What is the asymptotic running time of binary search on a sorted array?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 8

A nested loop has an outer loop of n iterations and an inner loop that doubles its index until it exceeds n. What is its growth?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 9

What is the asymptotic solution of T(n)=2T(n/2)+Θ(n)?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(2ⁿ)

Correct Answer: C. Θ(n log n)

Question 10

Which statement about Big-O notation is correct?

A. O(n²) is always a tight bound

B. A function in O(n) cannot also be in O(n²)

C. It gives an eventual upper bound up to a constant factor

D. It specifies exact execution time in seconds

Correct Answer: C. It gives an eventual upper bound up to a constant factor