1.
Introduction
2.
What is recurrence relation?
3.
What is the iteration method?
4.
Let us solve some of the problems using the iteration method
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Iteration Method

0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This blog aims to familiarise you with the iteration method. We will solve some exciting questions and algorithms using the iteration method.

To brush up on your knowledge of the basic complexity, you can read the article Time and Space complexity on Coding Ninjas Studio.

What is recurrence relation?

A relation that expresses the nth term of a sequence as a sum of k smaller terms is known as a recurrence relation.

Some of the examples of recurrence relation are:

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

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

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

The above examples show the nth term T(N) represented as a sum of K smaller terms.

Also see,  Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

What is the iteration method?

We solve recurrence relations using the iteration method. In this method, we keep substituting the smaller terms again and again until we reach the base condition. Thus the base term can be replaced by its value, and we get the value of the expression.

Let us solve some of the problems using the iteration method

1. Solve the following recurrence relation:

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

Solution:

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

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

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

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

From the above pattern, we get T(N) = T(N- (N-1)) + (N-1)

Thus T(N) = T(1) + (N-1) and since T(1)=1, T(N)=N.

Figure 1: Working of the recurrence relation T(N) = T(N-1) +1

Thus we found that T(N) = N using the iteration method.

2. Find the time complexity for the following recurrence relation:

T(N) = T(N-1) + c, T(1) = c, c is constant

Solution:

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

Thus T(N) = (T(N-2) + c )  + c

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

T(N) = T(N-3) + 3c

From the above pattern, we get T(N) = T(N- (N-1)) + (N-1)*c

Thus T(N) = T(1) + (N-1)*c and since T(1)=c, T(N)=N*c.

Now, as c is constant T(N) = O(N).

Thus we found that T(N) = O(N) using the iteration method.

3. 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))

Thus T(N) = T(1) + N + (N-1) + (N-2) + â€¦ (2) and since T(1)=1,

T(N)=N + (N-1) + (N-2) + â€¦ 1

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

Ans: Thus the time complexity is O(N2)

4. Solve the following recurrence relation:

T(N) = 2xT(N-1) , T(1) = 1

Solution:

Here T(N) = 2x T(N-1)  implies T(N-1) = 2xT(N-2).

T(N) = 2 x (2 x T(N-2) ) = 4  x T(N-2) = 22 x T(N-2)

T(N) = 8 x T(N-3)  = 23 x T(N-3)

Thus from the above patterns we get T(N) = 2N-1 x T(N- (N-1)) = 2N-1  x T(1) = 2N-1

Thus T(N) = 2N-1

5. Using the recurrence for the binary search given below, find the time complexity of binary search:

T(N) = T(N/2) + 1 , T(1) = 1

T(N) = T(N/2) + 1 = (T(N/4) + 1) + 1 = T(N/4) + 2

Thus T(N) = T(N/2k) + k

Now we choose k such that N/2k = 1

Thus N = 2=> k= log2(N)

Thus T(N) = T(1) + log2(N).

Since T(1) = 1, we get T(N) = log2(N) + 1

Figure 2: Binary Search algorithm

Thus the time complexity of the binary search algorithm is O(log2(N))

6. Solve the following recurrence relation:

T(N) = 2xT(N/2) , T(1) = 1

Solution: Here T(N) = 2x T(N/2)

Thus T(N) = 4T(N/4)

Thus T(N) = 2kT(N/2k)

Now we choose k such that N/2k = 1

Thus N = 2=> k= log2(N)

Thus T(N) = N x T(1)

Since T(1) = 1, T(N) = N.

7. Using the recurrence for merge sort given below find the time complexity of merge sort:

T(N) = 2xT(N/2) + N , T(1) = 1

T(N) =2x T(N/2) +  N=  2 x (2x(T(N/4) + N/4)) + N

T(N) = 4T(N/4) + 2N = 22T(N/22) + 2N

T(N) = 23T(N/23) + 3N

Thus T(N) = 2kT(N/2k) + kN

Now we choose k such that N/2k = 1

Thus N = 2=> k= log2(N)

Thus T(N) = NT(1)+ log2(N) x N.

Since T(1) =1, T(N) = N + log2(N) x N

Thus T(N) = N x (1+log2(N)) = O(N x log2(N))

Thus the time complexity of merge sort is Nlog2(N).

Also see, Morris Traversal for Inorder and Data Structure.

FAQs

1. What is the iteration method?
In this method, we keep on substituting the smaller terms again and again until we reach the base condition. Thus the base term can be replaced by its value, and we get the value of the expression.

2. What are the other methods to determine the time complexity in a program?
In this blog, we had solved most of the recurrence problems using the iteration method. The other methods to solve the recurrence are substitution method, Master theorem and Recursion Tree.

3. What is the use of the iteration method when we can find the time complexity quickly using the Master theorem?
The Master theorem may not be applicable over recurrence like T(N) = T(N-1) + N. In such cases, we need to solve using the iteration method.

4. Why do we need to find the time complexity?
Using time complexity, we can optimise an algorithm. The Iteration method helps us find the time complexity.

5. How can we optimize time complexity in a program?
We can use proper data structure along with the appropriate algorithms to optimize the time complexity.

Key Takeaways

We solve some exciting problems using the iteration method. We found time complexity for some famous recurrences and some famous algorithms like merge sort and binary search using iteration method.