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?