Iteration Method (Expansion Method)

The Iteration Method (also called the Expansion Method) is one of the simplest and most intuitive techniques for solving recurrence relations.

---

1. Introduction

The Iteration Method solves a recurrence by repeatedly expanding the recursive term until the base case is reached.

Instead of solving the recurrence directly, we

1. Expand the recurrence repeatedly.
2. Identify a pattern.
3. Generalize the pattern.
4. Stop when the base case is reached.
5. Substitute the stopping condition.
6. Simplify the expression.

Because the recurrence is expanded repeatedly, this method is also known as the Expansion Method.

---

General Procedure

Suppose the recurrence is

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

The steps are:

Step 1

Write the recurrence.

Step 2

Expand the recursive term once.

Step 3

Expand again.

Step 4

Continue until a pattern appears.

Step 5

Express the recurrence after $k$ expansions.

Step 6

Determine the value of $k$ using the stopping condition.

Step 7

Substitute $k$ and simplify.

---

Example 1: Binary Search

Consider

$$T(n)=T(n/2)+1$$

with

$$T(1)=1$$

---

First Expansion

$$T(n) = T(n/2)+1$$

---

Second Expansion

Expand $T(n/2)$

$$T(n) = T(n/4)+1+1$$
$$= T(n/4)+2$$

---

Third Expansion

$$T(n) = T(n/8)+3$$

---

Fourth Expansion

$$T(n) = T(n/16)+4$$

---

Pattern

After $k$ expansions,

$$\boxed{ T(n) = T\left(\frac{n}{2^k}\right)+k }$$

---

Stopping Condition

Recursion stops when

$$\frac{n}{2^k}=1$$

Therefore,

$$2^k=n$$

Taking logarithm,

$$k=\log_2n$$

---

Substitute

$$T(n) = T(1)+\log n$$

Since

$$T(1)=1$$
$$T(n) = 1+\log n$$

---

Final Answer

$$\boxed{ T(n)=\Theta(\log n) }$$

---

Example 2: Linear Recurrence

Consider

$$T(n)=T(n-1)+1$$

---

Expansion

$$T(n) = T(n-1)+1$$
$$= T(n-2)+2$$
$$= T(n-3)+3$$
$$= T(n-4)+4$$

---

Pattern

After $k$ expansions,

$$T(n) = T(n-k)+k$$

---

Stopping Condition

Stop when

$$n-k=1$$

Therefore,

$$k=n-1$$

---

Substitute

$$T(n) = T(1)+n-1$$

---

Final Answer

$$\boxed{ T(n)=\Theta(n) }$$

---

Example 3: Merge Sort

Consider

$$T(n)=2T(n/2)+n$$

---

First Expansion

$$T(n) = 2T(n/2)+n$$

---

Second Expansion

Expand

$$T(n/2) = 2T(n/4)+n/2$$

Substitute

$$T(n) = 2 \left( 2T(n/4)+n/2 \right) +n$$

Simplify

$$= 4T(n/4)+2n$$

---

Third Expansion

Expand again

$$T(n/4) = 2T(n/8)+n/4$$

Substitute

$$T(n) = 4 \left( 2T(n/8)+n/4 \right) +2n$$
$$= 8T(n/8)+3n$$

---

Fourth Expansion

$$T(n) = 16T(n/16)+4n$$

---

Pattern

After $k$ expansions,

$$\boxed{ T(n) = 2^k T \left( \frac{n}{2^k} \right) + kn }$$

---

Stopping Condition

Recursion stops when

$$\frac{n}{2^k}=1$$

Hence,

$$k=\log n$$

---

Substitute

$$T(n) = 2^{\log n} T(1) + n\log n$$

Since

$$2^{\log n}=n$$
$$T(n) = n+n\log n$$

---

Final Answer

$$\boxed{ T(n)=\Theta(n\log n) }$$

---

Example 4: A More Interesting Example

Solve

$$T(n)=3T(n/2)+n$$

---

Expansion

First

$$T(n) = 3T(n/2)+n$$

---

Second

$$= 3 \left( 3T(n/4)+n/2 \right) +n$$
$$= 9T(n/4) +\frac32n+n$$
$$= 9T(n/4) +\frac52n$$

---

Third

$$= 27T(n/8) +\frac{19}{4}n$$

The coefficients become complicated.

Instead of expanding indefinitely, observe the general pattern.

---

Pattern

After $k$ expansions,

$$T(n) = 3^k T \left( \frac{n}{2^k} \right) + n \sum_{i=0}^{k-1} \left(\frac32\right)^i$$

---

Stopping Condition

$$\frac{n}{2^k}=1$$
$$k=\log_2n$$

---

Substitute

$$T(n) = 3^{\log_2n} + n \sum_{i=0}^{\log n-1} \left(\frac32\right)^i$$

Since

$$3^{\log_2n} = n^{\log_23}$$

and the geometric series is dominated by its last term,

$$T(n) = \Theta(n^{\log_23})$$

---

Example 5: Constant Work

Solve

$$T(n)=2T(n/2)+1$$

---

Expansion

$$T(n) = 2T(n/2)+1$$
$$= 4T(n/4)+3$$
$$= 8T(n/8)+7$$
$$= 16T(n/16)+15$$

---

Pattern

$$T(n) = 2^k T(n/2^k) + (2^k-1)$$

---

Stopping Condition

$$k=\log n$$

---

Substitute

$$T(n) = nT(1)+n-1$$

---

Answer

$$\boxed{ T(n)=\Theta(n) }$$

---

Advantages of the Iteration Method

• Easy to understand.
• Simple to apply to many recurrences.
• Helps identify patterns.
• Provides intuition about recursive algorithms.
• Useful before learning the Master Theorem.

---

Limitations

• Expansion can become lengthy.
• Patterns may be difficult to recognize for complex recurrences.
• Algebra can become cumbersome.
• Not suitable for every recurrence.

---

Comparison with Other Methods

Method	Idea	Best Use
Iteration (Expansion)	Expand recursively until the base case	Learning and simple recurrences
Substitution	Guess the solution and prove by induction	General recurrences
Recursion Tree	Compute the cost level by level	Divide-and-conquer algorithms
Master Theorem	Apply a theorem directly	Standard recurrences of the form     $aT(n/b)+f(n)$
Akra–Bazzi Method	Generalization using calculus	Unequal-sized subproblems

---

Summary

The Iteration Method solves recurrence relations by repeatedly expanding the recursive term until the base case is reached. After each expansion, a pattern is identified and generalized for 

$k$expansions. By using the stopping condition, the value of $k$ is determined, and the final asymptotic solution is obtained.

The key idea is:

1. Expand the recurrence repeatedly.
2. Identify the general pattern.
3. Find the stopping condition.
4. Substitute the stopping value.
5. Simplify to obtain the asymptotic complexity.

For introductory algorithm analysis courses, the iteration method provides an intuitive bridge between recursive algorithms and more formal techniques such as the recursion tree method and the Master Theorem. It also helps students understand how recurrence relations evolve through successive recursive calls before moving on to more advanced solution techniques.