Recurrence Relations and Solving Methods

Recurrence relations are mathematical equations or inequalities that define a sequence where each term is given as a function of its preceding terms. They are fundamental in computer science for analyzing the time complexity and space complexity of recursive algorithms, providing a precise way to understand how an algorithm's runtime scales with input size.

1. What is a Recurrence Relation?

A recurrence relation expresses the value of a function $T(n)$ (often representing time or space complexity) in terms of its values on smaller inputs, typically $T(k)$ where $k < n$ . It consists of two main parts:

Base Case: Defines the value of $T(n)$ for a small, fixed input (e.g., $T(0)$ , $T(1)$ ), which stops the recursion.
Recursive Case: Defines $T(n)$ for larger inputs in terms of $T(k)$ for smaller .

For example, the running time of an algorithm that divides a problem of size $n$ into two subproblems of size $n/2$ and then combines their results in $O(n)$ time can be expressed as:

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

with a base case like $T(1) = O(1)$ .

2. Methods for Solving Recurrence Relations

Solving a recurrence relation means finding a closed-form solution, a non-recursive function of $n$ that describes $T(n)$ . There are several common methods:

Substitution Method: Guess a solution and verify it using mathematical induction.
Iteration Method (or Unrolling Method): Expand the recurrence repeatedly, identify a pattern, and sum the terms.
Recursion Tree Method: Visualize the recursive calls as a tree to sum costs at each level.
Master Method: A direct formula for a specific class of recurrence relations.

3. Substitution Method

The Substitution Method involves two main steps:

Guess the form of the solution: This often requires intuition, which can be gained from experience or by using other methods like the recursion tree.
Use mathematical induction to prove the guess:
- Base case: Show the guess holds for small values of $n$ .
- Inductive step: Assume the guess holds for all $k < n$ and use the recurrence to show it holds for $n$ .
- Solve for constants: Determine the constants to satisfy the inequality.

Example: Power Function

Consider the recurrence for computing $x^n$ :

cpp

double power(double x, int n) {
    if (n == 0) return 1;
    else return x * power(x, n - 1);
}

The recurrence relation for its time complexity is $T(n) = T(n-1) + c$ for $n > 0$ , and $T(0) = c_0$ , where and are constants.

Guess: $T(n) = O(n)$ . Let's try to prove $T(n) \le C n$ for some constant $C$ and $n \ge n_0$ .

Base Case: For $n=0$ , $T(0) = c_0 \le C \cdot 0$ is not possible unless $c_0 = 0$ . Let's try . For , . Let .

Inductive Step: Assume $T(k) \le C k + c_0$ for all $k < n$ . Then $T (n) = T (n - 1) + c \leq (C (n$ . We want . This implies , or . So, if we choose and , the solution holds.

Example: Recursive Fibonacci (as per source approximation)

Consider the recursive Fibonacci sequence algorithm:

T(n) = T(n-1) + T(n-2) + c \quad \text{for } n > 1

T(0) = c_0, T(1) = c_1

To simplify, the source suggests approximating $T(n-1) \approx T(n-2)$ , which makes $T(n) \approx 2T(n-1) + c$ . This approximation is generally loose but can give an upper bound.

Applying Iteration/Substitution with this approximation:

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

= 2(2T(n-2) + c) + c = 4T(n-2) + 2c + c = 4T(n-2) + 3c

= 4(2T(n-3) + c) + 3c = 8T(n-3) + 4c + 3c = 8T(n-3) + 7c

Following this pattern, after $k$ substitutions:

T(n) = 2^k T(n-k) + (2^k - 1)c

Let $n-k=0 \implies k=n$ . Substitute $k=n$ :

T(n) = 2^n T(0) + (2^n - 1)c

Since $T(0) = c_0$ (a constant), $T(n) = c_0 \cdot 2^n + (2^n - 1)c = (c_0+c)2^n - c$ . Thus, , which is exponential.

4. Iteration Method

The Iteration Method (also known as the Unrolling Method) involves repeatedly substituting the recurrence into itself until the base case is reached. This process helps reveal a pattern that can then be expressed as a summation.

Expand the recurrence: Substitute $T(n-1)$ , $T(n-2)$ , or $T(n/2)$ , etc., into the original equation multiple times.
Identify a pattern: Look for a general form of the terms after $k$ expansions.
Determine the number of iterations: Find such that the subproblem size reaches the base case.

Example: $T(n) = T(n/2) + c$

Let $T(1) = c_0$ .

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

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

= (T(n/8) + c) + 2c = T(n/8) + 3c

After $k$ iterations:

T(n) = T(n/2^k) + kc

The recursion stops when $n/2^k = 1$ , which means $2^k = n$ , so $k = \log_2 n$ . Substitute into the equation:

T(n) = T(1) + (\log_2 n)c

Since $T(1) = c_0$ (a constant):

T(n) = c_0 + c \log_2 n

Thus, $T(n) = O(\log n)$ .

5. Recursion Tree Method

The Recursion Tree Method provides a visual way to analyze recurrences. Each node in the tree represents the cost of a subproblem. The total cost is the sum of costs at all nodes.

Draw the tree: For $T(n) = aT(n/b) + f(n)$ , the root is $f(n)$ . It has $a$ children, each representing $T (n / b$ and having a cost of .

Example: $T(n) = T(n/4) + T(n/2) + n^2$

Let's visualize the recursion tree:

text

                               n^2
                             /     \
                            /       \
                       T(n/4)       T(n/2)
                       /  \         /  \
                      /    \       /    \
                 T(n/16) T(n/8) T(n/8) T(n/4)
                 ...

Costs at each level:

Level 0 (Root): $n^2$
Level 1: $(n/4)^2 + (n/2)^2 = n^2/16 + n^2/4 = 5n^2/16$

Total Cost: The total cost $T(n)$ is the sum of costs at all levels:

T(n) = n^2 + \frac{5}{16}n^2 + \left(\frac{5}{16}\right)^2 n^2 + \dots + \text{cost at leaves}

This is a geometric series with ratio $r = 5/16$ . Since $0 < r < 1$ , the sum converges. The sum of an infinite geometric series $a + ar + ar^2 + \dots$ is .

T(n) = n^2 \sum_{k=0}^{\infty} \left(\frac{5}{16}\right)^k = n^2 \frac{1}{1 - 5/16} = n^2 \frac{1}{11/16} = \frac{16}{11}n^2

Therefore, $T(n) = O(n^2)$ .

6. Master Method

The Master Method (or Master Theorem) provides a straightforward way to solve recurrences of the form:

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

where $a \ge 1$ and $b > 1$ are constants, $f(n)$ is an asymptotically positive function, and $n/b$ can be $\lfloor n/b \rfloor$ or .

The theorem describes three cases:

Case 1: If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$ (i.e., is polynomially smaller than ), then

T(n) = \Theta(n^{\log_b a})

Case 2: If $f(n) = \Theta(n^{\log_b a})$ (i.e., $f(n)$ is asymptotically equal to ), then

T(n) = \Theta(n^{\log_b a} \log n)

Case 3: If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$ (i.e., is polynomially larger than ), AND it satisfies the (for some constant and all sufficiently large , ), then

T(n) = \Theta(f(n))

Examples for Master Method:

Example 1 (Case 1): $T(n) = 3T(n/2) + O(n)$
- $a=3$ , $b=2$ , .

7. Example: Tower of Hanoi

The Tower of Hanoi is a classic puzzle that demonstrates recursive problem-solving. It involves moving $n$ disks from a source peg to a destination peg using an auxiliary peg, with rules:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one stack and placing it on top of another stack or on an empty rod.
No larger disk may be placed on top of a smaller disk.

The recursive solution breaks down into three steps:

Move $n-1$ disks from the source peg to the auxiliary peg.
Move the largest disk (the $n$ -th disk) from the source peg to the destination peg.
Move $n-1$ disks from the auxiliary peg to the destination peg.

Let $T(n)$ be the number of moves required for $n$ disks.

Base Case: $T(1) = 1$ (moving one disk takes one step).
Recursive Case: $T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1$ .

Solving $T(n) = 2T(n-1) + 1$ (by Iteration):

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

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

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

After $k$ iterations:

T(n) = 2^k T(n-k) + (2^{k-1} + \dots + 2^1 + 2^0)

The sum $2^{k-1} + \dots + 2^0$ is a geometric series sum $2^k - 1$ .

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

The recursion stops when $n-k = 1$ , so $k = n-1$ . Substitute $k=n-1$ :

T(n) = 2^{n-1} T(1) + (2^{n-1} - 1)

Since $T(1) = 1$ :

T(n) = 2^{n-1} \cdot 1 + 2^{n-1} - 1 = 2 \cdot 2^{n-1} - 1 = 2^n - 1

The time complexity is $T(n) = O(2^n)$ .

C++ Code Example: Tower of Hanoi

cpp

#include <iostream>
#include <vector>
#include <string>
 
// Function to solve Tower of Hanoi puzzle
// n: number of disks
// source: starting peg
// auxiliary: intermediate peg
// destination: target peg
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    // Base case: If there's only one disk, move it directly from source to destination
    if (n == 1) {
        std::cout << "Move disk 1 from " << source << " to " << destination << std::endl;
        return;
    }
 
    // Step 1: Move n-1 disks from source to auxiliary, using destination as temporary
    towerOfHanoi(n - 1, source, destination, auxiliary);

8. Example: Fibonacci Sequence (Recursive)

The Fibonacci sequence is defined as $F_0=0, F_1=1$ , and $F_n = F_{n-1} + F_{n-2}$ for . A direct recursive implementation leads to the recurrence:

T(n) = T(n-1) + T(n-2) + c \quad \text{for } n \ge 2

T(0) = c_0, T(1) = c_1

As shown earlier in the substitution method, this recurrence yields an exponential time complexity of $O(2^n)$ due to redundant computations (many subproblems are solved multiple times). While the exact solution involves the golden ratio, for a basic upper bound, the approximation to $2T(n-1)+c$ suffices to show its exponential nature.

Summary

Recurrence relations are fundamental for analyzing the time and space complexity of recursive algorithms.
A recurrence consists of a base case and a recursive case.
The Substitution Method involves guessing a solution and proving it using mathematical induction.
The Iteration Method unfolds the recurrence, identifies a pattern, and sums the costs to find a closed form.
The Recursion Tree Method visually represents recursive calls and their costs, making it easier to sum costs per level and derive a solution or a good guess.
The Master Method offers a direct solution for recurrences of the form $T(n) = aT(n/b) + f(n)$ by comparing $f(n)$ with across three cases.

Assessed progress

Recurrence Relations and Solving Methods

Recurrence Relations and Solving Methods

1. What is a Recurrence Relation?

2. Methods for Solving Recurrence Relations

3. Substitution Method

Example: Power Function

Example: Recursive Fibonacci (as per source approximation)

4. Iteration Method

Example: $T(n) = T(n/2) + c$

5. Recursion Tree Method

Example: $T(n) = T(n/4) + T(n/2) + n^2$

6. Master Method

Examples for Master Method:

7. Example: Tower of Hanoi

C++ Code Example: Tower of Hanoi

8. Example: Fibonacci Sequence (Recursive)

Summary

Key Concepts

Recurrence Relation

Substitution Method

Iteration Method

Recursion Tree Method

Master Method

Quick Check

Advanced Data Structures

Advanced Data Structures