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.

Answer 1

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)).