# 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

{% hint style="info" %}
Related homework questions: h2-Q7
{% endhint %}

### EGVS method

4 stages: **E**xpand, **G**uess, **V**erify and **S**top-and-Sum.

**Example:**

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

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. Guess:

   $$
   \begin{gather\*} T(n) = 2^i T({n\over{2^i}}) + i n \end{gather\*}
   $$
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. 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

{% hint style="info" %}
Related homework questions: h3-Q1
{% endhint %}

#### 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

{% hint style="info" %}
Related homework questions: h3-Q2
{% endhint %}

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](https://4258085521-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9G7bk8jPRz85XaeJtlxH%2Fuploads%2Fgit-blob-ef58671ba26829f81559fa116a4d34de5998a7e9%2Fsummation-rules-examples.png?alt=media)

## Transformation Techniques

### Domain Transformation

{% hint style="info" %}
Related homework questions: h3-Q3 and h3-Q4(combining range transformation)
{% endhint %}

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\*}
$$

{% hint style="info" %}
On Lecture II Page 46, L1120, we get the exact sum by transforming the descending sum to the ascending sum.
{% endhint %}

### Range Transformation

{% hint style="info" %}
Related homework questions: h3-Q4(combining domain transformation)
{% endhint %}

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

{% hint style="info" %}
Related homework questions: h2-Q8
{% endhint %}

**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)}$$

> Useful link: [Online basic master theorem solver](https://www.nayuki.io/page/master-theorem-solver-javascript)

### 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

{% hint style="info" %}
Related homework questions: h3-Q5
{% endhint %}

$$
\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

{% hint style="info" %}
Related homework questions: h2-Q9
{% endhint %}