Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
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 R-F Sep 9 '12 at 14:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.