📘
📘
📘
📘
Notes
Fundamental Algorithms
Search
⌃K

# Recurrences

Separable form for recurrence relation:
$\begin{gather*} T(n) = G(n, T(n_1), ..., T(n_k)) \end{gather*}$
where
$G(x_0, x_1, ..., x_k)$
is a function in
$k+1$
variables and each
$n_i (i=1,...,k)$
is a function of
$n$
that is strictly less than
$n$
.
Fibonacci sequence is defined by the recurrence relation:
$\begin{gather*} F(n) = F(n-1) + F(n-2) \end{gather*}$
For this, we have
$k=2, n_1=n-1, n_2=n-2$
$\begin{gather*} G(n, x, y) = x + y \end{gather*}$
Merge sort complexity:
$\begin{gather*} T(n) = n + 2T(n/2) \end{gather*}$
For this, we have
$k=1, n_1=n/2$
$\begin{gather*} G(n, x) = n + 2x \end{gather*}$

## Rote Method

Related homework questions: h2-Q7

### EGVS method

4 stages: Expand, Guess, Verify and Stop-and-Sum.
Example:
$T(n) = 2T(n/2) + n$
1. 1.
Expand:
\begin{align*} T(n) &= 2T(n/2) + n \\ &= 2 (2 T(n/4) + (n/2)) + n \\ &= 4 T(n/4) + 2n \\ &= 4 (2T(n/8) + (n/4)) + 2n \\ &= 8T(n/8) + 3n \\ &= \dots \end{align*}
2. 2.
Guess:
$\begin{gather*} T(n) = 2^i T({n\over{2^i}}) + i n \end{gather*}$
3. 3.
Verify: (use natural induction)
Base case:
$T(n)_{i=1} = 2T(n/2) + n$
holds
Inductive step: Assume
$T(n)_{i=k}$
holds, the goal is to prove
$T(n)_{i=k+1}$
also holds.
\begin{align*} T(n) &= 2^k T({n\over{2^k}}) + k n \\ &= 2^k (2 T({n\over{2^{k+1}}}) + {n\over{2^k}}) + k n \\ &= 2^{k+1} T(n/2^{k+1}) + （k+1) n \end{align*}
Therefore, this proves
$T(n)_{i=k+1}$
also holds.
Combining the base case and the inductive step we verified that
$T(n) = 2^i T({n\over{2^i}}) + i n$
.
4. 4.
Stop:
We can pick
$i = \lfloor {\lg n} \rfloor$
for stopping, then
$0 < {n\over{2^i}} \le 2$
.
By DIC, choose
$T(n) = 0$
for all
$n \le 2$
.
Therefore, for
$n > 1$
,
$\begin{gather*} T(n) = \lfloor {\lg n} \rfloor n \end{gather*}$

### Basic Sums

Other kinds of sums are often reduces to the following forms.

#### Arithmetic Sums

$\begin{gather*} S^k_n := \sum^n_{i=1}{i^k} \end{gather*}$
Solution:
$S^k_n = \Theta(n^{k+1})$

#### Geometric Sums

When
$x \ne 1$
,
$\begin{gather*} S_n(x) := \sum^{n-1}_{i=0}{x^i} \end{gather*}$
Solution:
$S_\infty = {{x^n - 1}\over{x - 1}}$

#### Infinite Geometric Series

When
$\lvert{x}\rvert < 1$
,
$\begin{gather*} S_{\infty}(x) := \sum^{\infty}_{i=0}{x^i} \end{gather*}$
Solution:
$S_{\infty}={1\over{1 - x}}$

#### Harmonic Series

$\begin{gather*} H_n := 1 + {1\over{2}} + {1\over{3}} + \dots + {1\over{n}} \end{gather*}$
Solution:
$H_n = ln(n) + g(n)$
where
$0 < g(n) < 1$
.

## Summation Techniques

### Growth Types

Related homework questions: h3-Q1

#### Polynomial Type

A real function
$f$
is polynomial-type if
$f$
is non-decreasing (ev.) and there is some
$C > 1$
such that:
$\begin{gather*} f(x) \le C f(x/2)\ (ev.) \end{gather*}$

#### Increasing Exponential Type

$f$
increases exponentially if there exists real numbers
$C > 1$
and
$k > 0$
such that:
$\begin{gather*} f(x) \ge C f(x - k)\ (ev.) \end{gather*}$

#### Decreasing Exponential Type

$f$
decreases exponentially if there exists real numbers
$C > 1$
and
$k > 0$
such that:
$\begin{gather*} f(x) \le f(x - k) / C\ (ev.) \end{gather*}$

#### Lemma 8: Closed Properties

(a) Polynomial-type functions are closed under addition, multiplication, and raising to any positive power
$a > 0$
.
(b) Exponential-type functions
$f$
are closed under addition, multiplication, and raising to any power
$a$
. In case
$a > 0$
, the function
$f^a$
will not change its subtype (increasing or decreasing). In case
$a < 0$
, the function
$f^a$
will change its subtype.
(c) If
$f$
is polynomial-type and
$\lg f$
is non-decreasing then
$\lg f$
is also polynomial-type. If
$f$
is exponential-type and
$a > 1$
then so is
$a ^ f$
.

### Summation Rules by Growth Type

Related homework questions: h3-Q2
Theorem 6: Summation Rules
$S_f(n) = \Theta \begin{cases} n f(n) & \text{if f is polynomial-type,} \\ f(n) & \text{if f is increasing exponentially,} \\ 1 & \text{if f is decreasing exponentially.} \end{cases}$
Examples:
• Polynomial Sums:
$\sum^n_{i\ge{1}}{i \log(i)} = \Theta(n^2 \log(n)), \sum^n_{i\ge{1}}{\log(i)} = \Theta(n \log(n)), \sum^n_{i\ge{1}}{i^a} = \Theta(n^{a+1})(a\ge{0}).$
• Exponentially Increasing Sums:
$\sum^n_{i\ge{1}}{b^i} = \Theta(b^n)(b\ge{0}), \sum^n_{i\ge{1}}{i^{-5}2^{2^i}} = \Theta(n^{-5}2^{2^n}), \sum^n_{i\ge{1}}{i!} = \Theta(n!).$
• Exponentially Decreasing Sums:
$\sum^n_{i\ge{1}}{b^{-i}} = \Theta(1)(b\ge{0}), \sum^n_{i\ge{1}}{i^2 i^{-i}} = \Theta(1), \sum^n_{i\ge{1}}{i^{-i}} = \Theta(1).$ More Examples

## Transformation Techniques

### Domain Transformation

Related homework questions: h3-Q3 and h3-Q4(combining range transformation)
Example:
Consider:
$\begin{gather*} T(N) = T(N/2) + N \end{gather*}$
We define
$t(n) := T(2^n) \text{or} N = 2^n$
.
This transforms the original N-domain into the n-domain:
\begin{align*} T(2^n) &= T(2^n/2) + 2^n \\ T(2^n) &= T(2^{n-1}) + 2^n \\ t(n) &= t(n-1) + 2^n \end{align*}
We get this standard form. By DIC, we choose the boundary condition
$t(n) = 0$
for all
$n \le 0$
.
We get sum:
$\begin{gather*} t(n) = \sum^n_{i\ge{0}}{2^n}=\Theta(2^n) \end{gather*}$
Because we have
$n = \lg N$
,
$\begin{gather*} T(N) = \Theta(N) \end{gather*}$
On Lecture II Page 46, L1120, we get the exact sum by transforming the descending sum to the ascending sum.

### Range Transformation

Related homework questions: h3-Q4(combining domain transformation)
Example:
$\begin{gather*} T(n) = 2T(n-1) + n \end{gather*}$
We define
$t(n) := {T(n)\over{2^n}}$
, then divide the both sides of the original equation by
$2^n$
.
\begin{align*} {T(n)\over{2^n}} &= 2{T(n-1)\over{2^n}} + {n\over{2^n}} \\ {T(n)\over{2^n}} &= {T(n-1)\over{2^{n-1}}} + {n\over{2^n}} \\ t(n) &= t(n-1) + {n\over{2^n}} \end{align*}
We get this standard form. By DIC, we choose the boundary condition
$t(n) = 0$
for all
$n \le 0$
.
We get sum: (
$\sum^n_{i\ge{0}}{n\over{2^n}}$
is exponentially decreasing)
$\begin{gather*} t(n) = \sum^n_{i\ge{0}}{n\over{2^n}}=\Theta(1) \end{gather*}$
Because
$t(n) = {T(n)\over{2^n}}$
,
$\begin{gather*} T(n) = \Theta(2^n) \end{gather*}$

## Master Theorem

Related homework questions: h2-Q8
Master recurrence:
$\begin{gather*} T(n) = a T(n/b) + d(n) \end{gather*}$
where
$a > 0$
,
$b > 0$
are real constants and
$d(n)$
the driving/forcing function.
Watershed constant
$w = \log_b(a)$
Watershed function
$W(n) = n^w = n^{\log_b(a)}$

### Master Theorem

Theorem 10: Master Theorem on Lecture II Page 51, L1207
$\begin{gather*} T(n) = \Theta \begin{cases} n^w, & \text{if } d(n) = O(n^{w-\epsilon}) \text{ for some } \epsilon > 0, & CASE(-) \\ n^w \log(n), & \text{if } d(n) = \Theta(n^w), & CASE(0) \\ d(n), & \text{if } a\cdot d(n/b) \le c\cdot d(n) \text{ for some } 0 < c < 1. & CASE(+) \\ \end{cases} \end{gather*}$

### Extended Master Theorem

Theorem 12: Extended Master Theorem on Lecture II Page 54, L1282
$\begin{gather*} T(n) = \Theta \begin{cases} d(n), & \text{if } a\cdot d(n/b) \le c\cdot d(n) \text{ for some } 0 < c < 1. & CASE(+) \\ W(n)\log\log n, & \text{if } d(n) = \Theta(W(n)\log^c(n)) \text{ for } c = -1, & CASE(1) \\ W(n)\log^{c+1}(n), & \text{if } d(n) = \Theta(W(n)\log^c(n)) \text{ for } c > -1, & CASE(0) \\ W(n), & \text{if } d(n) = O(W(n)\log^c(n)) \text{ for } c < -1. & CASE(-) \\ \end{cases} \end{gather*}$

## Multi-term Master Recurrences

Related homework questions: h3-Q5
$\begin{gather*} T(n) = d(n) + \sum_{i=1}^{k}{a_i T(n/b_i)} \end{gather*}$
where
$a_i > 0$
and
$b_1 > b_2 > \cdots > b_k > 1$
are real constants.
Watershed constant
It is the real number
$\alpha$
such that:
\begin{align*} 1 = \sum_{i=1}^{k}{a_i\over{b_i^{\alpha}}} \end{align*}
It clearly exists and is unique.

### Multi-term Master Theorem

Theorem 15: Multi-term Master Theorem on Lecture II Page 62, L1483
$\begin{gather*} T(n) = \Theta \begin{cases} n^{\alpha}, & \text{if } d(n) = O(n^{w-\epsilon}) \text{ for some } \epsilon > 0, & CASE(-) \\ n^w, & \text{if } d(n) = \Theta(n^w), & CASE(0) \\ d(n), & \text{if } \sum^k_{i=1}{a_i\cdot d(n/{b_i})} \le c\cdot d(n), & CASE(+) \\ \end{cases} \end{gather*}$

## Real Induction

Related homework questions: h2-Q9