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).
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!.