0

How to calculate time complexity for multiple nested loops? I have done this code but get confused about the time complexity of this! 

for(i=0; i<max; i++)
{
    for(j=0; j<max; j++)
    {
        a[i][j]= rand()%2;
    }
}

for(i=0; i<max; i++)
{
    for(j=0; j<max; j++)
    {

        if(a[j][i]==1)
        {
            inD++;
        }
    }
}
for(i=0; i<max; i++)
{
    for(j=0; j<max; j++)
    {
         if(a[i][j]==1)
         {
             outD++;
         }
    }
}
Fahim Rayhan
  • 11
  • 4

1 Answers1

0

You have three loops. Let's take the first one.

The outer loop is running max times, and each pass through that loop is running the inner loop max times, making max * max calls to a[i][j]= rand()%2; in total. Each call generates a random number: I don't know what the cost of this is but it's independent of max. The cost of this loop is O(max^2).

The other two loops have similar complexity except each inner call is essentially constant time since they're just increments.

Assuming they run one after the other, the whole thing is O(max^2 + max^2 + max^2) = O(max^2).

This answer spells it out in a bit more detail: Time complexity of nested for-loop