-1
$\begingroup$

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.

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

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++;
      }
  }
}

$\endgroup$

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