# Asymptotic Analysis of Nested Loops with Conditionals

I'm trying to run an analysis of a set of nested loops so that I can determine the value of variable sum after the outer loop is finished. The code is as follows:

sum = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < i*i; j++) {
if (j % i == 0) {
for (k = 0; k < j; k++) {
sum++
}
}
}
}


Note that this code is in C++. I have no problem doing this sort of analysis via summations for each loop, but the nested 'if' conditional is throwing me off. Here's what I have so far:

• The 3rd loop is only entered if j is equal to or a multiple of i.
• The outer and innermost loops have simple bounds that can easily be solved via summation.

Where I get hung up is in regard to defining the lower and upper bounds for the second loop when representing via summation. My current equation is:

$$\sum_{i=0}^{n-1} \sum_{???}^{i*i-1} \sum_{k=0}^{j-1}$$

I'm subtracting 1 from the upper bounds since the lower bounds start at 0, not 1.

Does anyone have any advice on how to represent this set of nested loops as summations that I can solve to determine the final value of sum? Any help is greatly appreciated.

• Step 1: Nested sums with the if. Step 2: Try to express the terms for which the if is false; subtract them. – Raphael Mar 7 '20 at 0:41
• Exact duplicate of a recent question, therefore most likely homework. – gnasher729 Mar 7 '20 at 17:44
• In C/C++, for(i = 0; i < n; i++) runs $n$ times (count the 0!) – vonbrand Mar 7 '20 at 22:29

The condition i % j == 0 is satisfied when j is equal to m * i for each m = 0, ..., i - 1. Therefore, the condition in the second loop will be satisfied i times. In form of summation this can be written as:

$$\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j * i - 1}$$

Moreover, your code is equivalent to:

sum = 0
for (i = 0; i < n; i++) {
for (j = 0; j < i; j++) {
for (k = 0; k < j * i; k++) {
sum++;
}
}
}