-
A recurrence is an equation that describes a function in terms of its value on smaller inputs.
-
We can solve recurrences using the following approaches
-
Substitution - Guess the form of the solution and then use mathematical induction to find the constraints and show the solution works.
-
Repertoire Method 1 - first find settings of general parameters for which the solution is known
Then obtain the general case by combining the special cases.
-
This method is built upon the possibility of combining two recurrences, which usually comes from using linear combinations. In particular, let
be a linear recurrence relation.
We identify building blocks (functions) of
that can be linearly combined The consider the generalized representation
And solve the simpler recurrences
The set of
forms the repertoire. We then determine the constants
and deduce the solution for The constant
is determined using the initial condition
-
-
Recursion Tree Method. We draw out a recursion tree where each node represents the cost of a single subproblem. We then sum all the costs per level of the tree, and then across all levels to obtain the cost of the whole tree.
We typically use this to make an ansatz that can be further refined.
-
-
Master Method. This allows us to solve recurrences of the form
Where
and are constants and is an asymptotically positive function. We implicitly assume that the problem is divided into equal subproblems
Let
denote the critical exponent has the following asymptotic bounds 2 3 -
If
then If the time to divide is dominated by the time to conquer, then the splitting term does not appear.
-
If
, where , then If the time to divide is equivalent to the time to conquer, then we have a splitting term
- If
, then - If
, then - If
, then
- If
-
If
and if for and sufficiently large (this additional constraint is the regularity condition), then . If the time to divide dominates the time to conquer, this doesn’t yield anything unless the regularity condition holds.
-
-
The Akra-Bazzi method is a generalization of the master theorem that assumes subproblems are divided into equal sizes.
We can apply the method to recurrences of the form
-
We assume the following:
There are sufficient base cases provided
and are constants such that and . where is a constant . is constant -
The asymptotic behavior of
is found by determining the value of for which And
-