Total number of iterations through loops?

Question

for(int i = 0; i < n-1; i++) {
    for(int j = i+1; j <= n; j++) {

    }
}

How do I figure out the number of iterations through these loops as a summation in terms of n?

Answer 1

If you can't run the code, you can look at the for loops:

for(int i = 0; i < n-1; i++)
for(int j = i+1; j <= n; j++)

The first loop runs n-1 times. The second loop runs n-i-1 times (for each i).

So the total loop runs is the summation from 0 to n-2 of n-i-1, or sigma(i=0,i<n-2,n-i-1).

• If n=0 it loops 0 times.
• If n=1 it loops 0 times.
• If n=2 it loops 2 times.
• If n=3 it loops 5 times.

Answer 2

Here's a simple way to approach this:

int numMult = 0;    
for(int i = 0; i < n-1; i++){
    for(int j = i+1; j <= n; j++){
        c[i][j] = a[i][j] * b[i][j];
        numMult++;
    }
}
System.out.println(numMult);