0
$\begingroup$

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?

2 Answers 2

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

1

Since your inner loops ensure that $i< j , 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.

  • 0
    Now I see, $t$hanks! +12012-09-09