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?

It's not so bad, except for the innermost loop — what the heck is for k=1 to k supposed to mean? Typo I assume — BrianO, Feb 05 '16 at 01:55
for j=1 to i^2 do { if(j (mod i) = 0) { f(j) }} can be simplified to for m = 1 to i { f(m*i) } — DanielV, Feb 05 '16 at 02:11
Another way to look at it: The only $j$ values for which we actually do any work (except check j (mod i) = 0) are the values $i, 2i, 3i, 4i, \ldots, i^2$. If you make $j$ just iterate over those values without taking any of the other values between $1$ and $i^2$, the if statement will always be true and you can get rid of it. — David K, Feb 05 '16 at 07:36
Another thought is, set $n=3$, and simulate the entire program by hand, counting how many times you increment sum and what the values of i, j, and k were each time. Then maybe you'll see a pattern. — David K, Feb 05 '16 at 07:42

Andrew Au · Answer 1 · 2016-02-05T06:13:52.060

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.

edited Feb 05 '16 at 06:13

answered Feb 05 '16 at 02:10

Andrew Au

1,127

I am still stuck. – MortalMan Feb 05 '16 at 03:05
How did you determine that the third loop runs j^2 times? – MortalMan Feb 05 '16 at 14:48
This is exactly the hint I told you. The $ k $ loop will execute only if $ j $ is a multiple of $ i $. The j mod i == 0 check will guarantee that. – Andrew Au Feb 05 '16 at 15:54
Oh that makes sense, thanks! – MortalMan Feb 05 '16 at 15:59

DanielV · Answer 2 · 2016-02-05T19:32:45.493

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}$$

I don't understand the first step you did, letting m = sqrt(j). Why? — MortalMan, Feb 05 '16 at 14:52
@MortalMan You are right, I should have said let $m = j/i$. The point is that the only values of $j$ that make it past the if statement are $j = i$, $j = 2i$, $j = 3i$ $\dots$. That is, only for $j = mi$ for $m$ in $1$ to $i$. — DanielV, Feb 05 '16 at 19:34

Analyze for loop with if statement

2 Answers2