Iteration Method

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.

Click here to learn about: What is Recursion

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(N²)

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) = 2² x T(N-2)

T(N) = 8 x T(N-3)  = 2³ x T(N-3)

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

Thus T(N) = 2^N-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/2^k) + k

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

Thus N = 2^k => 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) = 2^kT(N/2^k)

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

Thus N = 2^k => 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 = 2²T(N/2²) + 2N 

T(N) = 2³T(N/2³) + 3N 

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

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

Thus N = 2^k => 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.

To learn more about the iteration method, you can read this article.

Read More - Time Complexity of Sorting Algorithms

Check out Coding Ninjas Studio to learn more about competitive programming, DSA, attempt mock tests, interview preparation, and much more.

Happy Learning!!!