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!

  • $\begingroup$ That’s unlikely since the outer two loops take n log n already. $\endgroup$
    – gnasher729
    Mar 30 '20 at 17:40
  • $\begingroup$ Log log n is not (log^2) n $\endgroup$
    – gnasher729
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.