Comment by mxwsn

Since collisions between two objects are symmetric (object one colliding with object two is the same event as object two colliding with object one) there are n(n-1)/2 possible collisions. The guy's probably short handing this as O(n^2), which is the important relationship as he's motivating the example by the need to handle collisions between large numbers of particles in hair, and modeling hair with as large a number of separate elements as possible is probably the key to realistic simulation.