Big-Oh of for loop with if-else statement

Question

I'm wondering why is the tightest Big-Oh Complexity of the following code O(n^4) instead of O(n^5):

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

Can anyone help me with this? Thank you!

Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, Jun 11 '20 at 14:15
The inner `sum++` operation gets executed sum(sum(i*j for j=1..(i-1)) for i=1..(n-1)) times. That's exactly 1/24 n (n + 1) (n + 2) (3 n + 1). — Paul Hankin, Jun 11 '20 at 14:25

score 0 · Answer 1 · answered Jun 11 '20 at 14:14

0

From math we know that a number x has at most 2*x^0.5 divisors.
So if statement will be executed j^0.5 times in worst case
which equals to n since largest j is n*n

answered Jun 11 '20 at 14:14

Photon

2,717
1
18
22

score 0 · Answer 2 · answered Jun 11 '20 at 14:31

0

It backs to the inner-most if condition. As j%i == 0 is only true for j = {i, 2*i, 3*i, ..., i * i}, just i times the second loop will run in O(i^2). Hence, the tight complexity is O(n^4).

answered Jun 11 '20 at 14:31

OmG

18,337
10
57
90

Big-Oh of for loop with if-else statement

2 Answers2