Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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!
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.
