TABLE OF CONTENTS:
1. Recurrence Relation
2. Recurrence : Substitution Method
3. Recurrence : Iterative Method
4. Examples to show Substitution Method
5. Examples to show Iterative Method
6. Advantages and Disadvantages
of Substitution Method
7. Advantages and disadvantages
of Iterative Method
8. Algorithmic relation between
iteration and recursion with an example ( Fibonacci series)
9. A coarse method for finding complexity in recurrence
9.1 Method of determining order of complexity
10. Analyzing running time with recurrence relations
11. Conclusion
12. References
1. Recurrence Relation:
When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence. A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs.
• The recurrence is based on the three steps of the paradigm:
• T(n) – running time on a problem of size n
• Divide the problem into a subproblems, each of size n/b:
• Conquer (solve) the subproblems [aT(n/b)]
• Combine the solutions [Cn]
In the “substitution method”, we guess a bound and then use mathematical induction to prove our guess correct.
The “iteration method” converts the recurrence into a summation and then relies on techniques for bounding summations to solve the recurrence.
The “master method” provides bounds for recurrences of the form
T(n) = aT(n/b) + f(n)
Where a ≥ 1, b > 1, and f(n) is a given function; it requires memorization of three cases, but once you do that, determining asymptotic bounds for many simple recurrences is easy.
2. Recurrence: The substitution method
→The substitution method for solving recurrences involves guessing the form of the solution and then using mathematical induction to find the constants and show that the solution works.
→The name comes from the substitution of the guessed answer for the function when the inductive hypothesis is applied to smaller values.
In sort substitution method is :
• Guessing the form of the solution and
• proving the solution
→This method is powerful, but it obviously can be applied only in cases when it is easy to guess the form of the answer.
→The substitution method can be used to establish either upper or lower bounds on a recurrence.
3. Recurrence: The iteration method
• The method of iteration a recurrence doesn’t require us to guess the answer. But it may require more algebra than the substitution method.
“The idea is to expand (iterate) the recurrence and express it as a summation of terms dependent only on n and the initial conditions.”
• Techniques for evaluating summations can then be used to provide bounds on the solution
The iteration method usually leads to lots of algebra, and keeping everything straight can be a challenge. The key is to focus on two parameters: the number of times the recurrence needs to be iterated to reach the boundary condition, and the sum of the terms arising from each level of the iteration process.]
The master theorem is another important method in solving recurrences.
4. Example to show substitution method:
Prove that using the substitution method.
Solution:
T(n)=T(n/2)+√n = T(n/4)+ √(n/2)+ √n=…= T(n/2i) + √(n/2i-1) +…+ √n
Guess: T(n) = O(√n), meaning T(n) ≤ c√n
Induction base: n = 1, c=4
T(1) = 1 ≤ c√1 , c > 0
Induction step:
T(n) = T(n/2) + √n = k we have
s(n) = ck + s(n-k)
But “if k = n”
s(n) = cn + s(0) = cn
Example 2:
T(n) =
2T(n/2) + c
So expanding the terms we have,
2(2T(n/2/2) + c) + c
22T(n/22) + 2c + c
22(2T(n/22/2) + c) + 3c
23T(n/23) + 4c + 3c
23T(n/23) + 7c
23(2T(n/23/2) + c) + 7c
24T(n/24) + 15c
…
2kT(n/2k) + (2k – 1)c [general form]
6. Advantages and Disadvantages of Substitution Method
Advantages :
• Mathematically rigorous.
• Can solve any recurrence relation
• Can prove exact or asymptotic solutions.
Disadvantages :
• Need to guess the correct solution
• Difficult to use this method
7. Advantages and Disadvantages of Iterative Method
Advantages:
• Very simple
• Can compute exact and asymptotic solutions
Disadvantages :
• Not mathematically rigorous;
• Difficult to solve some recurrence.
Example : T(n) = T(2n/3) + T(n/3) + n
T(n) = T (n/4) +T(n/2) + 1
8. Algorithmic relation between iteration and recursion with an example ( Fibonacci series)
Example : Fibonacci series
Fibonacci series is defined as follows:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
Problem :
1. To find an iterative algorithm and a recursive one for computing element number n in Fibonacci series, Fibonacci(n).
2. To Analyze the running-time of each algorithm.
a. Recursive Computation:
recFib(n) {
if (n ≤ 1)
return n
else
return recFib(n-1) + recFib(n-2)
}
T(n) = T(n-1) + T(n-2)
2T(n-2) ≤ T(n-1) + T(n-2) ≤ 2T(n-1)
T(n) = O(2n)
T(n) = Ω(2n/2)
b. Iterative Computation:
Iterative computation:
IterFib (n) {
f[0] = 0;
f[1] = 1;
for ( i=2 ; i ≤ n ; i++)
f[i] = f[i-1] + f[i-2];
}
T(n) = O(n)
9. A coarse method for finding complexity in recurrence
9.1 Method of Determining Order of Complexity:
One can determine the “approximate” order of complexity of a function by examining the ratio of the Nth term compared to the N+1st term. I.e., if F is a recurrence relation then examine F(N+1) compared to F(N) as N grows.
Of course this ratio tends to infinity since growth functions are normally monotonically increasing but one may make a more discriminating comparison by computing a function that the ratio tends to.
10. Analyzing running time with recurrence relations
Asymptotic complexity has limitations, but it is still a useful tool analyzing and improving program performance.
The use of big-O notation simplifies the task of analyzing performance.
The recurrence relation is an inductive definition of a function.
T(n) = T(n-1) + c1 for n > 0
T(0) = c2
This particular recurrence relation has a unique closed-form solution that defines T(n) without any recursion. In order to determine the running time of recursive functions we will write recurrences that describe the running time, find closed form solutions to them, and express those solutions in terms of Big-Oh notation.
Expanding out this particular recurrence gives some idea of how to convert it to closed form:
T(n) = T(n-1) + c1 for n > 0
= T(n-2) + c1 + c1
= T(n-3) + c1 + c1 + c1
= T(n-k) + kc1 for n,k > 0 and k < n
= T(0) + nc1 for n > 0
= c2 + nc1 for n > 0
which is O(n).
More generally, we guess a closed form solution for a recurrence, and then prove by induction that it holds. Sometimes expanding out the recurrence for a few steps can help with guessing.
11. Conclusion:
From the above discussions it is clear that solving Recurrence relation using Substitution and Iterative Method can be implemented on various operations and types of applications to improve its efficiency and consistency.
12. References:
http://homepages.ius.edu
http://www.cs.virginia.edu/~luebke/cs332/index.html
http://www.cs.cornell.edu/Courses/cs3110/2009sp/lectures/lec19.html
