Modulo complexity within nested loop

Question

i have following code:

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

How would if (j % i == 0) affect the overall complexity? As k goes up to j, which is n*n, the third loop should also be of complexity n*n= O(n^2), am i right? So it would be O(N)*(N^2)*(N^2)= O(n^5)? But the solution given is O(n^4), so where am i wrong? Thanks!

I'm familiar with the basic concepts of BigOh, but i'm not understanding this specific case, as my calculations for the sum of the nested loops (with the first one repeating the second one n times and the second one repeating the third one n^2 times and the third one being n^2 also would sum up to n^5) differs from what i know it is (n^4). So it has to be something about if (j % i == 0) that reduces the exponent by one. As j is in average way bigger than i, there should be a good possibility that if (j % i == 0) is fulfilled. But why does it decrease the overall complexity's exponent exactly by one ? I have searched Google at SE but i didn't find any infos on a modulo integrated into a nested loop like this. Thanks in advance.

Answer 1

Given a loop

for i from 0 to n exclusive:
  if i is divisible by a:
    f(i)

we can see that f(i) will be executed n/a times (to be precise: 1 + floor((n-1)/a) for n > 0 times). The running time for this subexpression would then be T(n) = ∑i=0...(n-1)/a F(a·i). In your specific case, my a is not a constant, and will therefore cancel out one n.

Answer 2

This isn't actually an answer to your exact question; more like an alternative way of going at things. If you don't need a theoretically sound answer and simply want to know whether your code will perform well enough for larger input sizes, there's a simple way to determine the answer to questions like that empirically. Especially if you can't figure out the theoretical bounds and you already have the basic code structure in place.

Add a counter variable to the innermost loop. Basically, you already have one (sum). Run your code for a few different sizes of n, say for n=100, 1000, 1e4, 1e5, 1e6 etc and look at how your counter grows. Use finer-grained steps if the running time for larger values of n grows prohibitive. You can graph the resulting data using a spreadsheet and get an idea as to how similar the graph looks to standard time complexity functions.

When your loops and branching logic get more complicated, often that's the quickest way to get some insight into how your code will actually behave. If you add two counters, one inside the branch and one outside, you can also get a feeling for how many times the branch is not taken.

This also helps to validate answers you arrive at by reasoning about time complexity in a more formal manner.