Time complexity of nested for loop with inner iteration variable dependent on the outer one

Question

This is the loop structure :

for (int i = 1 ; i < n ; i++) {
    for (int j = 0 ; j < n ; j += i) {
        // do stuff
    }
}

My guess was O(nlogn) as it clearly cannot be O(n^2) since the increment in j is increasing and it clearly cannot be O(n sqrt(n)) since the increment is not that high. But I have no idea how to prove it formally.

OmG · Accepted Answer · 2018-03-12 13:19:54Z

5

Each time complexity of the inner loop is based on the value of i is n/i. Hence, total time would be n + n/2 + n/3 + ... + n/n = n(1+1/2+1/3+...+1/n). As we know 1+1/2+1/3+...+1/n is a harmonic sereis and asymptotically is log(n). Hence, the algorithm is run in O(nlog(n)).

answered Mar 12, 2018 at 13:19

OmG

19k13 gold badges69 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time complexity of nested for loop with inner iteration variable dependent on the outer one

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related