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++;
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?
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.