3 ms·
> 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 secon
by rflrob 16y ago
> 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!.
- revolvingcur 16y agoYeah, that analysis is egregiously wrong: the terms should be summed instead of multiplied. The correct complexity is O(n^2).
- IvoDankolov 16y agoActually, 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),