[dahart]

As others have pointed out, it's order n^2, not meant to be interpreted as exactly n^2. I will add that, having done hair simulation for DreamWorks, it's likely that their collision simulations are done on guide hairs, rather than interpolated hairs. So n is usually more like 1k, not 100k. Complete accuracy of hair simulations in film isn't required, nobody will notice individual hairs crossing each other, but you might notice big clumps behaving badly.