Triples algorithm complexity

Question

This not optimal algorithm count the number of distinct triples $(i, j, k)$ such that $a[i] + a[j] + a[k] = 0$.

public static int count(int[] a) {
    int N = a.length;
    int cnt = 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 (a[i] + a[j] + a[k] == 0) {
                    cnt++;
                }
            }
        }
    }
    return cnt;
}

Trying to estimate the complexity of this algorithm It's clear that there are 3 nested loops.

• First one loops from $0$ $\to$ $N$; $N$ times exactly.
• Second one loops from $1$ $\to$ $N$; $(N-1)$ times exactly.
• Third one loops from $2$ $\to$ $N$; $(N-2)$ times exactly.

For me the inner if statement will execute $N(N-1)(N-2)$ times. But I'm wrong. Experimental data throws me something like $N (N-1)(N-2)/6$.

How this 6 division factor appear?

Answer 1

Your error is assuming that the second loop always starts from $1$. It starts from one more than whichever number the outer loop has reached -- that is, a different number of times each time it is reached.

Similarly, the innermost loop doesn't always start from $2$.

The precise factor of $1/6$ comes from binomial coefficients. The number of different $k$-element subsets of an $N$-element set is $$\binom{N}{k} = \frac{N!}{k!(N-k)!} = \frac{N(N-1)\cdots(N-k+1)}{k!}$$ and $\frac{1}{3!}$ is $\frac {1}{6}$.

Answer 2

Since your inner loops ensure that $i< j <k$, the inner if is executed as many times as there are unordered triples from $\{1,\ldots,n\}$. Which is $\binom{n}{3} = \frac16n(n-1)(n-2)$.

Edit: To see why the number of unordered triples is the quoted quantity, observe that every such triple can be ordered 6 ways, so there are 6 times as many ordered triples. Now the number of ordered triples is just $n(n-1)(n-2)$, since you can choose the first in $n$ ways, then the next in $n-1$ ways and the last in $n-2$ ways. See here for the general version.