Analyze for loop with if statement

Question

I have this rather complicated loop:

sum=0
for i=1 to n do
    for j=1 to i^2 do
        if(j (mod i) = 0) then
            for k=1 to j do
                sum++

How the heck do I analyze this? I would try to use a sum but the if statement throws me off. How can I determine what time this nested for loop runs in?

Answer 1

The code is essentially this:

sum=0
for i=1 to n do
    for j=1 to i do
        for k=1 to j^2 do
           sum++

The $ k $ loop executes $ j^2 $ times. The $ j $ loop executes $ i $ times

Therefore the time taken to execute all the iterations of a $ j $ loop is

$ \sum\limits_{j = 1}^{i}{j^2} = O(i^3) $

Finally, the $ i $ loop executes $ n $ times, the time taken to execute the whole program will be

$ \sum\limits_{i = 1}^{n}{O(i^3)} = O(n^4) $.

That's all.

Answer 2

sum=0
for i=1 to n do
    for j=1 to i^2 do
        if(j (mod i) = 0) then
            for k=1 to j do
                sum++

This is the same as

$$\begin{align} % S(n) &= \sum_{i = 1}^n \sum_{\begin{array} {l} j = 1 \\ j \equiv 0 \pmod i \end{array}}^{i^2} \sum_{k = 1}^j 1 % \\ \\ & \text{Let } m = j/i % \\ \\ &= \sum_{i = 1}^n \sum_{m = 1}^{i} \sum_{k = 1}^{m^2} 1 % \end{align}$$

You don't have to evaluate the sum exactly, all you need to be able to determine is that $\sum_{i = 1}^n \sum_{m = 1}^{i} \sum_{k = 1}^{m^2} 1$ is a 4th degree polynomial.

$$\begin{align} % S(n) &= \sum_{i = 1}^n \sum_{m = 1}^{i} m^2 % \\ \\ &= \sum_{i = 1}^n A~i^3 + \dots % \\ \\ &= A~n^4 + \dots % \end{align}$$

Since an increment takes a logarithmic amount of time to compute, your runtime is

$$\begin{align} % R(n) & \in O(S(n)\log(S(n)) % \\ \\ &= O(~ (A~n^4 + \dots) \log( An^4 + \dots)~) % \\ \\ &= O(n^4\log(n)) % \end{align}$$

---

The exact computation, which isn't necessary but might help understand, is:

$$\begin{align} % S(n) &= \sum_{i = 1}^n \sum_{m = 1}^{i} m^2 % \\ \\ &= \sum_{i = 1}^n \frac{1}{6}\bigg(2i^3 + 3i^2 + i\bigg) % \\ \\ &= \frac{1}{12} \bigg(n^4 + 4n^3 + 5n^2 + 2n\bigg) % \end{align}$$