📘
📘
📘
📘
Notes
Fundamental Algorithms
Blog
Search
⌃K
Links

Recurrences

Separable form for recurrence relation:
T(n)=G(n,T(n1),...,T(nk))\begin{gather*} T(n) = G(n, T(n_1), ..., T(n_k)) \end{gather*}
where
G(x0,x1,...,xk)G(x_0, x_1, ..., x_k)
 is a function in
k+1k+1
 variables and each
ni(i=1,...,k)n_i (i=1,...,k)
 is a function of
nn
 that is strictly less than
nn
.
Fibonacci sequence is defined by the recurrence relation:
F(n)=F(n−1)+F(n−2)\begin{gather*} F(n) = F(n-1) + F(n-2) \end{gather*}
For this, we have
k=2,n1=n−1,n2=n−2k=2, n_1=n-1, n_2=n-2
​
G(n,x,y)=x+y\begin{gather*} G(n, x, y) = x + y \end{gather*}
Merge sort complexity:
T(n)=n+2T(n/2)\begin{gather*} T(n) = n + 2T(n/2) \end{gather*}
For this, we have
k=1,n1=n/2k=1, n_1=n/2
​
G(n,x)=n+2x\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)+nT(n) = 2T(n/2) + n
​
  1. 1.
    Expand:
    T(n)=2T(n/2)+n=2(2T(n/4)+(n/2))+n=4T(n/4)+2n=4(2T(n/8)+(n/4))+2n=8T(n/8)+3n=…\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:
    T(n)=2iT(n2i)+in\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)+nT(n)_{i=1} = 2T(n/2) + n
     holds
    Inductive step: Assume
    T(n)i=kT(n)_{i=k}
     holds, the goal is to prove
    T(n)i=k+1T(n)_{i=k+1}
     also holds.
    T(n)=2kT(n2k)+kn=2k(2T(n2k+1)+n2k)+kn=2k+1T(n/2k+1)+（k+1)n\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+1T(n)_{i=k+1}
     also holds.
    Combining the base case and the inductive step we verified that
    T(n)=2iT(n2i)+inT(n) = 2^i T({n\over{2^i}}) + i n
    .
  4. 4.
    Stop:
    We can pick
    i=⌊lg⁡n⌋i = \lfloor {\lg n} \rfloor
     for stopping, then
    0<n2i≤20 < {n\over{2^i}} \le 2
    .
    By DIC, choose
    T(n)=0T(n) = 0
     for all
    n≤2n \le 2
    .
    Therefore, for
    n>1n > 1
    ,
    T(n)=⌊lg⁡n⌋n\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

Snk:=∑i=1nik\begin{gather*} S^k_n := \sum^n_{i=1}{i^k} \end{gather*}
Solution:
Snk=Θ(nk+1)S^k_n = \Theta(n^{k+1})
​

Geometric Sums

When
x≠1x \ne 1
,
Sn(x):=∑i=0n−1xi\begin{gather*} S_n(x) := \sum^{n-1}_{i=0}{x^i} \end{gather*}
Solution:
S∞=xn−1x−1S_\infty = {{x^n - 1}\over{x - 1}}
​

Infinite Geometric Series

When
∣x∣<1\lvert{x}\rvert < 1
,
S∞(x):=∑i=0∞xi\begin{gather*} S_{\infty}(x) := \sum^{\infty}_{i=0}{x^i} \end{gather*}
Solution:
S∞=11−xS_{\infty}={1\over{1 - x}}
​

Harmonic Series

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

Summation Techniques

Growth Types

Related homework questions: h3-Q1

Polynomial Type

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

Increasing Exponential Type

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

Decreasing Exponential Type

​
ff
 decreases exponentially if there exists real numbers
C>1C > 1
 and
k>0k > 0
 such that:
f(x)≤f(x−k)/C (ev.)\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>0a > 0
.
(b) Exponential-type functions
ff
 are closed under addition, multiplication, and raising to any power
aa
. In case
a>0a > 0
, the function
faf^a
 will not change its subtype (increasing or decreasing). In case
a<0a < 0
, the function
faf^a
 will change its subtype.
(c) If
ff
 is polynomial-type and
lg⁡f\lg f
 is non-decreasing then
lg⁡f\lg f
 is also polynomial-type. If
ff
 is exponential-type and
a>1a > 1
 then so is
afa ^ f
.

Summation Rules by Growth Type

Related homework questions: h3-Q2
Theorem 6: Summation Rules
Sf(n)=Θ{nf(n)if f is polynomial-type,f(n)if f is increasing exponentially,1if f is decreasing exponentially.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:
    ∑i≥1nilog⁡(i)=Θ(n2log⁡(n)),∑i≥1nlog⁡(i)=Θ(nlog⁡(n)),∑i≥1nia=Θ(na+1)(a≥0).\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:
    ∑i≥1nbi=Θ(bn)(b≥0),∑i≥1ni−522i=Θ(n−522n),∑i≥1ni!=Θ(n!).\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:
    ∑i≥1nb−i=Θ(1)(b≥0),∑i≥1ni2i−i=Θ(1),∑i≥1ni−i=Θ(1).\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:
T(N)=T(N/2)+N\begin{gather*} T(N) = T(N/2) + N \end{gather*}
We define
t(n):=T(2n)orN=2nt(n) := T(2^n) \text{or} N = 2^n
.
This transforms the original N-domain into the n-domain:
T(2n)=T(2n/2)+2nT(2n)=T(2n−1)+2nt(n)=t(n−1)+2n\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)=0t(n) = 0
 for all
n≤0n \le 0
.
We get sum:
t(n)=∑i≥0n2n=Θ(2n)\begin{gather*} t(n) = \sum^n_{i\ge{0}}{2^n}=\Theta(2^n) \end{gather*}
Because we have
n=lg⁡Nn = \lg N
,
T(N)=Θ(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:
T(n)=2T(n−1)+n\begin{gather*} T(n) = 2T(n-1) + n \end{gather*}
We define
t(n):=T(n)2nt(n) := {T(n)\over{2^n}}
, then divide the both sides of the original equation by
2n2^n
.
T(n)2n=2T(n−1)2n+n2nT(n)2n=T(n−1)2n−1+n2nt(n)=t(n−1)+n2n\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)=0t(n) = 0
 for all
n≤0n \le 0
.
We get sum: (
∑i≥0nn2n\sum^n_{i\ge{0}}{n\over{2^n}}
 is exponentially decreasing)
t(n)=∑i≥0nn2n=Θ(1)\begin{gather*} t(n) = \sum^n_{i\ge{0}}{n\over{2^n}}=\Theta(1) \end{gather*}
Because
t(n)=T(n)2nt(n) = {T(n)\over{2^n}}
,
T(n)=Θ(2n)\begin{gather*} T(n) = \Theta(2^n) \end{gather*}

Master Theorem

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

Master Theorem

Theorem 10: Master Theorem on Lecture II Page 51, L1207
T(n)=Θ{nw,if d(n)=O(nw−ϵ) for some ϵ>0,CASE(−)nwlog⁡(n),if d(n)=Θ(nw),CASE(0)d(n),if a⋅d(n/b)≤c⋅d(n) for some 0<c<1.CASE(+)\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
T(n)=Θ{d(n),if a⋅d(n/b)≤c⋅d(n) for some 0<c<1.CASE(+)W(n)log⁡log⁡n,if d(n)=Θ(W(n)log⁡c(n)) for c=−1,CASE(1)W(n)log⁡c+1(n),if d(n)=Θ(W(n)log⁡c(n)) for c>−1,CASE(0)W(n),if d(n)=O(W(n)log⁡c(n)) for c<−1.CASE(−)\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
T(n)=d(n)+∑i=1kaiT(n/bi)\begin{gather*} T(n) = d(n) + \sum_{i=1}^{k}{a_i T(n/b_i)} \end{gather*}
where
ai>0a_i > 0
 and
b1>b2>⋯>bk>1b_1 > b_2 > \cdots > b_k > 1
 are real constants.
Watershed constant
It is the real number
α\alpha
 such that:
1=∑i=1kaibiα\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
T(n)=Θ{nα,if d(n)=O(nw−ϵ) for some ϵ>0,CASE(−)nw,if d(n)=Θ(nw),CASE(0)d(n),if ∑i=1kai⋅d(n/bi)≤c⋅d(n),CASE(+)\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
Previous
Introduction
Next
Search Trees
Last modified 1yr ago