Time Complexity for Modulus in Nested Loops

user_15260005 0
Viewed 200
sum=0;
for(i=1; i<n;i++)
   for( j = 1; j < i * i; j++ ) 
      if( j % i == 0 )
        for( k = 0; k < j; k++ ) 
             sum++;

I know that the outer most loop executes n time, the next loop n^2 times, but how do I factor the j%i with the loop? The correct answer is O(N^4), but I am not sure how that is reached.

mod big-o for-loop java
1 Answers

Since we know that the k loop only executes when j is divisible by i (this is where the modulo comes in), we can figure out how many times k loops at every i loop:

  • i = 2, j:1..4: loops 2 times (j=2).
  • i = 3, j:1..9: loops 3 + 6 times (j=3,6).
  • i = 4, j:1..16: loops 4 + 8 + 12 times (j=4,8,12).
  • ...
  • i = n, j:1..n*n: loops n + 2n + ... (n - 1) * n
    • Or Sum(k * n, k = 1, n - 1) = n^2 * (n - 1) / 2 times.

I realize that this should stop at i = n - 1, but this is enough to show the growth.

This means that our complexity is that of

2 + (3 + 6) + (4 + 8 + 12) + ... + (n^2 * (n - 1) / 2)
=Sum(
  i^2 * (i - 1) / 2, 
  i = 2, n - 1
)
=Sum(
  (i^3 - i^2) / 2, 
  i = 2, n - 1
)

Since the i^3 term dominates and the division by 2 doesn't matter, this has the same time complexity as

Sum(i^3, i=2, n - 1)

Which is O(n^4).

user_42943990
Related