I often encounter a situation where I need all the objects in a scene to react to the positions of all other objects. One such example is when simulating flocking behaviour of hundreds of agents.

If we have **n** objects (or 'agents') in our scene, then every one of those **n** agents will need to check its position against every other agent.

In other words we will need to do **n²** comparisons.

If we have four agents which we name a, b, c, and d, then the required position comparisons would look something like this:

`aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd`

Thats 16 checks, giving us the running time: $$T(n) = O(n^2)$$
However, since checking the distance between two positions will be the same regardless of the direction we measure from, we can assume that ab = ba and so on.
`aa, ab, ac, ad, `~~ba~~, bb, bc, bd, ~~ca~~, ~~cb~~, cc, cd, ~~da~~, ~~db~~, ~~dc~~, dd

So the new amount of checks we need to do equals: $${n(n+1)} \over {2}$$
In addition, we won't have to check agent positions against themselves, so we can get rid of aa, bb, cc, and dd.

~~aa~~, ab, ac, ad, ~~ba~~, ~~bb~~, bc, bd, ~~ca~~, ~~cb~~, ~~cc~~, cd, ~~da~~, ~~db~~, ~~dc~~, ~~dd~~

Which is equivalent to summing all the numbers from one to n minus one. $$1+2+..+(n-1) = {n(n-1) \over 2}$$

The resulting loop:

```
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
// skip if we are checking against ourselves
if (i == j)
continue;
// pass direction vector info to agent[i] and agent[j]
Vector3 dir = agent[i] - agent[j];
agent[i].AddDirection (dir);
agent[j].AddDirection (dir * -1);
}
}
```

Notice that the integer **j**of the inner for loop is set to

**i**, so that as

**i**increases the number of iterations of the inner loop decreases. In the above demo this improved performance noticeably compared to the standard

**n²**checks.