Reccurences

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Searching #◇Data Structures #◇Search Efficiency #◇Analysis of Algorithms #◇Recursion #◇Sorting #◇Recursion and Iteration #◇Computational Complexity #◇Time Complexity #◇Space Complexity

◇Overview

A recurrence relation defines a sequence of values recursively: the value at a certain index is based on previous values in the sequence. These are...

◇Key Concepts

Base case Recursive case

◇Details / Theory

◇What are Recurrence Relations?

A recurrence relation defines a sequence of values recursively: the value at a certain index is based on previous values in the sequence. These are often used to express the running time of recursive algorithms.

◇What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem until a base condition is met.

Key Concepts:

Base case: the condition under which recursion ends. Recursive case: the part of the function where the recursion happens.

◇Examples of Recursive Algorithms

1. Factorial

Mathematical Definition:

$n! = \begin{cases} 1, & \text{if } n = 1 \\ n \cdot (n - 1)!, & \text{if } n > 1 \end{cases}$

Recursive Function (C Code):

int factorial(int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

Time Complexity Recurrence:

$T(n) = T(n - 1) + b, \quad T(1) = a$

By expanding:

$\begin{aligned} T(n) &= T(n - 1) + b \\ &= T(n - 2) + 2b \\ &= \ldots \\ &= T(1) + (n - 1)b = a + (n - 1)b \end{aligned}$

Final Time Complexity: $O(n)$

2. Power Function

Mathematical Definition:

$k^n = \begin{cases} 1, & \text{if } n = 0 \\ k \cdot k^{n-1}, & \text{if } n > 0 \end{cases}$

Recursive Function (C Code):

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

Time Complexity: $O(n)$

3. Fibonacci Numbers

Mathematical Definition:

$F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-1) + F(n-2), & \text{if } n > 1 \end{cases}$

Recursive Function:

int fib(int n) {
    if (n <= 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

Time Complexity: $O(2^n)$ due to overlapping subproblems.

Optimized (Dynamic Programming): $O(n)$

◇Solving Recurrence Relations

Three Primary Methods:

1. Iteration Method (Expand and derive pattern)
2. Substitution Method (Guess and prove by induction)
3. Master's Theorem (Used for divide-and-conquer)

Iteration Method Example

Given:

$T(n) = T(n - 1) + 3, \quad T(1) = 2$

Expanding:

$\begin{aligned} T(n) &= T(n - 1) + 3 \\ &= T(n - 2) + 6 \\ &= \ldots \\ &= T(1) + 3(n - 1) = 2 + 3(n - 1) = 3n - 1 \end{aligned}$

Time Complexity: $O(n)$

Master's Theorem (For Divide and Conquer)

For recurrences of the form:

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

where $a \geq 1$, $b > 1$, and $f(n)$ is asymptotically positive:

1. If $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$
2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, and if $af(n/b) \leq cf(n)$ for some $c < 1$ and large enough $n$, then $T(n) = \Theta(f(n))$

Examples of Divide and Conquer Recurrences

Binary Search

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

Using Master's Theorem:
$a = 1$, $b = 2$, $f(n) = c$ $n^{\log_b a} = n^{\log_2 1} = n^0 = 1$ Since $f(n) = c = \Theta(1) = \Theta(n^{\log_b a})$, case 2 applies Thus, $T(n) = \Theta(\log n)$

Merge Sort

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

Using Master's Theorem:
$a = 2$, $b = 2$, $f(n) = cn$ $n^{\log_b a} = n^{\log_2 2} = n^1 = n$ Since $f(n) = cn = \Theta(n) = \Theta(n^{\log_b a})$, case 2 applies Thus, $T(n) = \Theta(n \log n)$

◇Common Recurrence Relations and Their Solutions

◇Common Pitfalls

Forgetting the base case when writing a recurrence — without it, the recurrence has no termination and cannot be solved Misidentifying $a$, $b$, and $f(n)$ when applying the Master Theorem — $a$ is the number of subproblems, $b$ is the factor by which the input shrinks, and $f(n)$ is the non-recursive work Applying the Master Theorem to recurrences where it doesn't apply (e.g., $T(n) = 2T(n-1)$ is not in the form $T(n) = aT(n/b) + f(n)$) Incorrect substitution in the iteration method — always expand at least 3 levels and verify the pattern before generalizing Confusing $T(n) = 2T(n/2) + n$ ($O(n \log n)$, merge sort) with $T(n) = 2T(n/2) + 1$ ($O(n)$, binary tree traversal)

◇Summary

TL;DR — Recurrences model the running time of recursive algorithms. Solve them via iteration (expand and find a pattern), substitution (guess and verify), or the Master Theorem ($T(n) = aT(n/b) + f(n)$ with three cases). Key examples: binary search $O(\log n)$, merge sort $O(n \log n)$, Fibonacci $O(2^n)$.

◇Links

Related: Source / Reference:

◇References & Navigation

• Previous Topic: ◇Worst-case running time
• Next Topic: ◇Searching Algorithms
• Related Notes: ◇Recursion Tree Method, ◇Substitution Method