Mon May 02 2022 (5 months ago)
Engineer by mistake!
I am a software engineer by passion
Recurrence relation is an equation that expresses the nth term of a sequence as a function of k preceding terms, for some fixed k (independent from n), which is called the order of the relation. Once k initial terms of a sequence are given, the recurrence relation allows computing recursively all the remaining terms of the sequence.
Analyzing control statements are easy because they are iterative. Many algorithms are recursive in nature and when we analyze them we get a recurrence relation for time complexity.
We get running time as a function of n(input size) and we get the running time on inputs of smaller size.
A recurrence relation recursively defines a sequence where the next term is a function of previous term.
Homogeneous (characteristic equation)
Master Theorem ***
Recurrence tree ***
Intelligent guess work
Change of variable
In substitution method we make guess for the solution then we use mathematical induction to prove the guess is correct or incorrect. This is the most acceptable method as it always works for any recurrence relation, although it takes too much time in calculation.
is the time to solve instance of size n, and is the time to solve instance of size .
Replacing by and , we can write the following equations.
Substituting equation 3 in 2, we'll get equation 4 as follows:
By substituting equation 4 in 1, we'll get the following equation:
From above observation we can write the general form of the equation 1 as follows.
Suppose, if we take then,
If we rewrite the equation then we'll get that,
By relpacing by , we'll get the following
By replacing by , we'll get the following
If we substitute eq (3) into eq (2), then we'll get the following
Substituting the value of eq (4) into eq (1), we'll get the following
From the above observation, we can write the general form of the equation as below
Suppose if we take , then we could rewrite the above equation as follows.
The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm.
Suppose if we have the recurrence of the following form:
The above recurrence relation constitutes of three parts. is the time taken to solve a problem of size , is the number of sub-problems, is the time required to solve a sub-problem and is the time required divide and conquer the sub-problems.
There are three cases:
Case 1 : if is in , i.e then
Case 2 : if is in , i.e then
Case 3 : if is in , i.e then
Here, . So,
Case 2 applies :
Here, . So,
Case 2 applies :
Here, . So, and
Case 1 applies :
In recurrence tree method, each node represents the cost of a single sub-problem in the set of recursive function invocations. We sum the cost within each level of the tree to obtain a set of per level cost.
We sum the per level cost in-order to determine the total cost of the all levels of the recursion.
Here while solving the problem, we divide the problem into sub-problems of equal size.
where and is a given function.
is the cost of splitting and combining the sub-problems.
In the above diagram, a problem of size n has been divided into two sub-problems of size .
The recurrence tree for this recurrence is:
When we add the values across the levels of the recursion tree, we get a value of n for every level. The bottom level has nodes and each contributing of .
We have seen what are the recurrence relations and popular methods to solve them. We have also seen some examples for each method.
© 2021 dsabyte. All rights reserved