# Complexity of finding factors of factors of N number

for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j+=i)
for(int k = j; k <= N; k+=j)


How to express this mathematically to calculate the complexity of the above code. I guess, its complexity is $$O(N\log\log N)$$ but couldn't prove it mathematically!

• That’s unlikely since the outer two loops take n log n already. Mar 30 '20 at 17:40
• Log log n is not (log^2) n Mar 30 '20 at 17:42

For each value of $$j$$, the inner loop runs for $$O(N/j)$$ iterations. Fixing $$i$$ and varying over all $$j$$ in the middle loop, the total number of iterations in the inner loop is $$O(N/i + N/(2i) + N/(3i) + N/(ki)) = O(N\log k/i),$$ where $$ki$$ is the maximal multiple of $$i$$ which is at most $$N$$. We can bound $$k$$ by $$N/i$$, and so the expression above equals $$O(N\log (N/i)/i) = O(N\log N/i)$$. Summing over all $$i$$ from 1 to $$N$$, we get $$O(N\log^2 N)$$.
Using rudimentary calculus (approximating the sum by an integral), you can show that if you sum $$N\log (N/i)/i$$ over $$i$$ from 1 to $$N$$ then you still get $$\Theta(N\log^2 N)$$, and so the bound above should be tight.