Recurrences
Separable form for recurrence relation:
where
is a function in
variables and each
is a function of
that is strictly less than
.
Fibonacci sequence is defined by the recurrence relation:
For this, we have
Merge sort complexity:
For this, we have
Related homework questions: h2-Q7
4 stages: Expand, Guess, Verify and Stop-and-Sum.
Example:
- 1.Expand:
- 2.Guess:
- 3.Verify: (use natural induction)Base case:holdsInductive step: Assumeholds, the goal is to provealso holds.Therefore, this provesalso holds.Combining the base case and the inductive step we verified that.
- 4.Stop:We can pickfor stopping, then.By DIC, choosefor all.Therefore, for,
Other kinds of sums are often reduces to the following forms.
Solution:
When
,
Solution:
When
,
Solution:
Solution:
where
.
Related homework questions: h3-Q1
A real function
is polynomial-type if
is non-decreasing (ev.) and there is some
such that:
increases exponentially if there exists real numbers
and
such that:
decreases exponentially if there exists real numbers
and
such that:
(a) Polynomial-type functions are closed under addition, multiplication, and raising to any positive power
.
(b) Exponential-type functions
are closed under addition, multiplication, and raising to any power
. In case
, the function
will not change its subtype (increasing or decreasing). In case
, the function
will change its subtype.
(c) If
is polynomial-type and
is non-decreasing then
is also polynomial-type. If
is exponential-type and
then so is
.
Related homework questions: h3-Q2
Theorem 6: Summation Rules
Examples:
- Polynomial Sums:
- Exponentially Increasing Sums:
- Exponentially Decreasing Sums:

More Examples
Related homework questions: h3-Q3 and h3-Q4(combining range transformation)
Example:
Consider:
We define
.
This transforms the original N-domain into the n-domain:
We get this standard form. By DIC, we choose the boundary condition
for all
.
We get sum:
Because we have
,
On Lecture II Page 46, L1120, we get the exact sum by transforming the descending sum to the ascending sum.
Related homework questions: h3-Q4(combining domain transformation)
Example:
We define
, then divide the both sides of the original equation by
.
We get this standard form. By DIC, we choose the boundary condition
for all
.
We get sum: (
is exponentially decreasing)
Because
,
Related homework questions: h2-Q8
Master recurrence:
where
,
are real constants and
the driving/forcing function.
Watershed constant
Watershed function
Theorem 10: Master Theorem on Lecture II Page 51, L1207
Theorem 12: Extended Master Theorem on Lecture II Page 54, L1282
Related homework questions: h3-Q5
where
and
are real constants.
Watershed constant
It is the real number
such that:
It clearly exists and is unique.
Theorem 15: Multi-term Master Theorem on Lecture II Page 62, L1483
Related homework questions: h2-Q9
Last modified 1yr ago