# Triples algorithm complexity

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?

-

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}$.

-

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.

-
See the edit. Generally speaking, the 6 comes from 3! being the number of ways to order 3 things. So if there were $n$ loops, the factor would be $n!$ –  ronno Sep 9 '12 at 14:20
Now I see, thanks! +1 –  Randolf Rincón Fadul Sep 9 '12 at 14:20