SOLVING A RECURRENCE RELATION USING AN ITERATIVE METHOD

 

1. A recurrence relation is like a rule that tells us how to find the value of a function based on its previous values.
2. There are different methods for doing this, which basically involve finding patterns and using mathematical techniques to come up with the solution.
3. In this approach, we repeatedly replace smaller terms with their values until we reach the simplest form. Eventually, we can substitute the base term with its value, allowing us to find the overall value of the expression.
4. Iteration methods involve expanding a recurrence relation by expressing it as a sum of terms involving n and initial conditions.
5. This approach helps understand how the function grows with increasing input size n, making it easier to analyse its behaviour and time complexity.

This can be understood with the help of an example as follows :

 

Example1:

·       The Fibonacci sequence is defined recursively as : F(n) = F(n−1) + F(n−2) with base cases : F(0) = 0, F(1)= 1 where F(5) = ?

Solution : To solve this recurrence relation iteratively, we start with the base cases and work our way up to the desired term. Let's find F(5) using iteration:

1.    Base cases provide starting points for the sequence. Here, F(0) and F(1) are given directly, which we can use to build up the sequence.

2.    We use a loop to calculate Fibonacci numbers iteratively, starting from F(2) up to the desired value, in this case, F(5)

·       For each n, calculate F(n) by adding the previous two Fibonacci numbers : F(n) = F(n−1) + F(n−2).

·       For example : F(2) = F(1)+F(0) when n=2 and F(3) = F(2)+F(1) for n=3.

3.    Using this approach, we find:

        F(2) = F(1)+F(0) = 1+0 = 1

        F(3) = F(2)+F(1) = 1+1 = 2

        F(4) = F(3)+F(2) = 2+1 = 3

        F(5) = F(4)+F(3) = 3+2 =5

4.    After completing the iterations, we find the desired Fibonacci number, in this case F(5) = 5.

 

Example 2:

·       The Fibonacci sequence is defined recursively as : an​     = an−1​  + 2 with base case :  a0  ​= 1, Find  a5​ ​.

Solution :

1.    To solve this recurrence relation iteratively, we start with the base cases same as per the above example. Here, Let's find a5 using iteration:

2.    We then use a loop to calculate Fibonacci numbers iteratively, starting from n=1 up to the desired value, in this case, a5.

·       For each n, we use the recurrence relation an​  = an−1​ + 2 to find the next term.

      (We incrementally build up the sequence by adding 2 to the previous term.)

3.    In each iteration, we update the value of an−1​ to the current value of an​ and proceed to the next iteration.

4.    Let's perform the iterations:

• a1 = a0+2 = 1+2 =3
• a2 ​= a1 +2 = 3+2 = 5
• a3 = a2 ​+2 = 5+2 = 7
• a4 ​= a3 +2 = 7+2 = 9
• a5 = a4 ​​+2 = 9+2 = 11

    Hence we found the desired output, a5 ​= 11.

    In this way, we can solve recurrence relations iteratively by directly calculating each term based on the previous term and the given recurrence relation.

 

Now let us understand the time complexity. The time complexity of the iterative algorithm is typically easier to analyze than the recursive one because there’s no additional overhead from function calls. You can often express it directly in terms of the number of iterations or the operations performed in the loops.

 

Example : Find the time complexity for the following recurrence relation : T(N) = T(N-1) + N, T(1) = 1

Solution : Here T(N) = T(N-1) + N implies T(N-1) = T(N-2) + N-1.

Thus,

          T(N) = (T(N-2) + (N-1))  + N

          T(N) = T(N-2) + N + (N-1)

          T(N) = T(N-3) + N + (N-1) + (N-2)

          From the above pattern, we get

          T(N) = T(N-k) + N + (N-1) + (N-2) + … (N-(k-1))

          T(N) = T(1) + N + (N-1) + (N-2) + … (2) and since T(1)=1,

          T(N) = N + (N-1) + (N-2) + … (1)

          T(N) = N x (N-1)/2 = O(N*N)

Thus the time complexity is O(N²)

      

Top of Form

 

 

Meenal S. Shelar

S.Y. (AI) Rollno. 17