News for hackers. Stuff that matters.
Re:3D Theory - Collision Detection by rflrob on Sunday February 20, 2011 @12:26PM (#2242376)
> For example if we have 'n' objects then the first object could collide with n-1 objects (since we don't check if an object has collided with itself) the second object could collide with (n-2) additional objects not counting the possible collisions we have already counted. If we keep going like this we get the number of possible collisions is: (n-1) * (n-2) * (n-3) ... 1 This is equivalent to n! / 2! * (n-2)!

Seems to me like it should be more like the handshake problem, which comes out to n * (n-1)/2. n^2 is still bad, but not nearly as bad as n!.

Re:3D Theory - Collision Detection by IvoDankolov on Sunday February 20, 2011 @12:55PM (#2242478)
Actually, n! / (2! * (n-2)!) comes out exactly at n * (n-1)/2. It's just one form of the general formula for combinations.

However, multiplying the possible situations is, of course, wrong. A case of a wrong explanation of the final result I'd imagine (permutations instead of combinations),

Re:3D Theory - Collision Detection by revolvingcur on Sunday February 20, 2011 @12:46PM (#2242441)
Yeah, that analysis is egregiously wrong: the terms should be summed instead of multiplied. The correct complexity is O(n^2).