for loop

For Loop Analysis | The Complete Guide

In this article we will see about the for loops used in programming language. Looping statement helps us to a great extend. Let’s discuss about it.

Difficulty level : Easy

Introduction

Before heading into the analysis topic, let’s see some basic concept and examples.

Syntax

for (initializationStatement; testExpression; updateStatement)
 {  
   // statements inside the body of loop 
}

When it is used?

When we want to repeat a set of statements again and again we use for loop. This loop ensures that the set of statements we want to repeat gets executed till the desired number of times.

Example

// Print numbers from 1 to 10 #include <stdio.h>
 int main() 
{   
   int i;  
   for (i = 1; i < 11; ++i)  
    {    
        printf("%d ", i);
    }   
return 0;
 }

Note: This is just a simple example. We can also use for loop to do complex problems also.

For Loop

Whenever we want to repeat a set of instructions we used loops. For loop is the most used in while, do-while and for.

Whenever a set of instructions repeats it has a very high impact on algorithm speed.

In the previous post, we tell that worst case is most often use, so we analyze our for loop in a worst-case scenario

Similarly, In this post, we are going to learn how to analyze for loop to calculate the running time of the algorithm

After all, we had already discussed asymptotic notation and we know the best case, average case, and worst case.

In this post, we discuss the basic time complexity of for by the help of simple examples.

For Loop Analysis

1. O(1) in for loop

The time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion, call to any other non-constant time function and any repetitive statements.

For Example add function

void add(int a,int b)
{
int sum = a+b;
cout<<sum;
}

Another notable point is whenever a loop runs a constant number of time, it is treated as O(1). For Example,

for(int i = 0;i<C;i++)           //  C is constant
{
         //O(1) expressions
}

O(n)

Time Complexity of is considered as O(n) if variables are incremented/decremented by a constant amount. For example following functions have O(n) time complexity.

// Here c is a positive integer constant   

   for (int i = 1; i <= n; i = i + c) {  

        // some O(1) expressions

   }



   for (int i = n; i > 0; i = i - c) {

        // some O(1) expressions

   }

O(n^c)

The time complexity of nested loops is equal to the number of times the innermost statement is executed.

For example, the following sample loops have O(n2) time complexity and another one is O(n^3)

for(int i =0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
// Some O(1) Expressions
}
}

for(int i = 0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
for(int k = 0;k<n;k++)
// Some O(1) expressions
}
}
}

O(log(n))

Time Complexity of a loop is considered as O(log N) if the loop variables are divided/multiplied by a constant value.


   for (int i = 1; i <=n; i = i* c) {

       // some O(1) expressions

   }



   for (int i = n; i > 0; i = i / c) {

       // some O(1) expressions

   }

O(log(log(n)))

Time Complexity of a loop is considered as O(log log N). If the variables are reduced/increased exponentially by a constant amount.

 // Here c is a constant greater than 1   

   for (int i = 2; i <=n; i = pow(i,c)) { 

       // some O(1) expressions

   }

Consecutive For Loop’s

When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.

  for (int i = 1; i <=m; i += c) {  

        // some O(1) expressions

   }
   for (int i = 1; i <=n; i += c) {

        // some O(1) expressions

   }
   The time complexity of the above code is O(m) + O(n) which is O(m+n)

   If m == n, the time complexity becomes O(2n) which is O(n).

Time complexity when there are many if, else statements inside for loops?

As discussed earlier, the worst-case time complexity is the most useful among best, average and worst. Therefore we need to consider the worst case.

If there are any number of if-else condition then only we take if – else in consideration

For example, consider the linear search function where we considered the case when an element is present at the end or not present at all.

We can get an upper bound by ignoring if-else and other complex control statements,After all, when the code is too complex to consider all if-else cases.

Conclusion

In this article we discussed the basics and examples of for loop. Also, we had a detailed explanation for the analysis of time complexity of the for loops. Hope this article helped you understand this topic in a easier way. Leave your comments below to let us know if you have any query!

Sudhanshu is Technology geek and also a pro pubg player. I like to create content in my free time that helps others. Currently pursuing BCA from Noida and operating Geekstocode

Leave a Comment

Your email address will not be published. Required fields are marked *