Time complexity analysis by tracing the code in C++

An important aspect of competitive coding is analyzing the algorithms because in competitive coding apart from correctness, efficiency of algorithms also matters significantly. One the most important aspect of time complexity analysis is tracing the code carefully. For example consider the given below code snippets:-

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,c,j,n=3;    
 for(i=0,c=0;i<n;i++)
 {
    for(j=0;j<n;j++)
     {
        c++;
     }
}
cout<<c<<endl;
return 0;
}

Output :

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,c,j,n=3;    
for(i=0,j=0,c=0;i<=n;i++)
{      
     if(i==n)
      {
          i=0; j++;                  
      }
     if(j==n)
     {
        break;
     }   
     c++; 
}   

cout<<c<<endl;
return 0;
}

Output :

Important points to observe:

Although first algorithm looks like O(n^2) or in simpler terms appears to take more number of iterations as compared to second one which looks like O(n), both are equally fast and take equal number of iterations for a given value of n.
Moreover, if you print the value of c for a given n you will find that it will be equal in both the cases. For example if you take n as 3 then c will be 9 in both the cases.

Hence properly analyzing and tracing the code is really important while analyzing the time complexity of an algorithm.

Related tutorials