Calculating the number of times an if statement is executed

Question

This code counts how many integer triples sum to 0: The full code is here.

initialise an int array of length n
int cnt = 0 // cnt is the number of triples that sum to 0
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        for (int k = j+1; k < n; k++) {
            if (array[i]+array[j]+array[k] == 0) {
                cnt++;
            }
        }
    }
}

Now, from the book Algorithms by Robert Sedgewick, I read that:

• The initialisation of cnt to 0 is executed exactly once.
• cnt++ is executed from 0 to the number of times a triple is found.
• The if statement is executed n(n-1)(n-2)/6 times.

I've done some experiments and all of them are true. But I completely don't know how they calculate the number of times the if statement got executed. I'm not sure, but I think that:

• n means from i to n
• (n-1) means from i+1 to n
• (n-2) means from j+1 to n
• /6 I don't know what's this for.

Can anyone explain how to calculate this?

Answer 1

It's sum of sums.

1. The inner loop is executed n-j-1 times each time it is being reached
2. The middle loop is executed n-i-1 times each time it is being reached
3. The outer loop is executed n times.

Sum all of these and you get total number of times the cnt++ is invoked.

---

Note that the number of times the middle loop is executed each time is NOT n-1, it is n-i-1, where i is the index of the outer loop. Similarly for middle loop.

The /6 factor is coming from taking it into account in the summation formula.