Time Complexity of Nested for Loops with if Statements

user_12184630 0
Viewed 3346

How does the if-statement of this code affect the time complexity of this code?

Based off of this question: Runtime analysis, the for loop in the if statement would run n*n times. But in this code, j outpaces i so that once the second loop is run j = i^2. What does this make the time complexity of the third for loop then? I understand that the first for loop runs n times, the second runs n^2 times, and the third runs n^2 times for a certain amount of times when triggered. So the complexity would be given by n*n^2(xn^2) for which n is the number of times the if statement is true. The complexity is not simply O(n^6) because the if-statement is not true n times right? 

int n;
int sum;
for (int i = 1; i < n; i++)
{
  for (int j = 0; j < i*i; j++)
    {
      if (j % i == 0)
        {
          for (int k = 0; k < j; k++)
            {
              sum++;
            }           
        }       
    }   
}
big-o c c++
2 Answers

The if condition will be true when j is a multiple of i; this happens i times as j goes from 0 to i * i, so the third for loop runs only i times. The overall complexity is O(n^4).

for (int i = 1; i < n; i++)
{
  for (int j = 0; j < i*i; j++)       // Runs O(n) times
    {
      if (j % i == 0)                 // Runs O(n) × O(n^2) = O(n^3) times
        {
          for (int k = 0; k < j; k++) // Runs O(n) × O(n) = O(n^2) times
            {
              sum++;                  // Runs O(n^2) × O(n^2) = O(n^4) times
            }
        }
    }
}
user_74129860

The complexity is not simply O(n^6) because the if-statement is not true n times right?

No, it is not.

At worst, it is going to be O(n^5). It is less than that since j % i is equal to 0 only i times.

The first loop is run n times.
The second loop is run O(n^2) times.
The third loop is run at most O(n) times.

The worst combined complexity of the loop is going to be O(n) x O(n^2) x O(n), which is O(n^4).

user_4345510
Related