Recurrences
Last updated
Last updated
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:
4 stages: Expand, Guess, Verify and Stop-and-Sum.
Example:
Expand:
Guess:
Verify: (use natural induction)
Stop:
Other kinds of sums are often reduces to the following forms.
Theorem 6: Summation Rules
Examples:
Polynomial Sums:
Exponentially Increasing Sums:
Exponentially Decreasing Sums:
Example:
Consider:
This transforms the original N-domain into the n-domain:
We get sum:
Example:
Master recurrence:
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
Watershed constant
It clearly exists and is unique.
Theorem 15: Multi-term Master Theorem on Lecture II Page 62, L1483
For this, we have
Base case: holds
Inductive step: Assume holds, the goal is to prove also holds.
Therefore, this proves also holds.
Combining the base case and the inductive step we verified that .
We can pick for stopping, then .
By DIC, choose for all .
Therefore, for ,
Solution:
When ,
Solution:
When ,
Solution:
Solution: where .
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 .
We define .
We get this standard form. By DIC, we choose the boundary condition for all .
Because we have ,
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 ,
where , are real constants and the driving/forcing function.
Useful link:
where and are real constants.
It is the real number such that: