Complexity of two nested loops with the inner loops stepping dependend on the outer loops variable

Question

function(n) {
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j+=i)
            printf("*");
}

I thought this was O(n²logn), but the book says O(n*log(n)), so where am I going wrong?

Answer 1

for each value of i, inner loop executes (n-1)/i+1 times because for each i the inner loop executes according to following equation which satisfies an AP ie.. 1+(x-1)*i=n which implies x = (n-1)/i + 1

obviously it is going to form an AP. So now all you have to do is sum the expression for 1<=i<=n. that is

((n-1)/1 +1) + ((n-1)/2+1)+ ((n-1)/3+1) //upto n because max value of i can be n
that becomes n + Summation((n-1)/i) where i can go upto n.

Evaluation that you get O(nlogn) as complexity