Just to clarify, on re-reading the thing about O(n) or better sounded a little optimistic. I didn't do the math per se, but it's based on the idea that the more enemies there are, the further they must be away on average, and therefore the more liberties you can afford to take with approximation. You could also form ad-hoc squads in formation and only check for collisions between squads. If enemies frequently change squads it won't look too formation-based even if it is.