News for hackers. Stuff that matters.
Re:CoffeePhysics: A JS/CS Physics Engine by HardyLeung on Wednesday February 29, 2012 @10:59AM (#3648283)
You mean N^2, not N!
Re:CoffeePhysics: A JS/CS Physics Engine by nlogn on Wednesday February 29, 2012 @11:16AM (#3648346)
He's right actually if the code is written sensibly. Well it should really be (N-1)! but close enough. Think about it in terms of 3 balls. I check ball1 against ball2 and ball3 then move to ball2. It gains me nothing to re-check ball2 against ball1 so I just check it against ball3. When I reach ball3, I have already checked everything and I'm done.

The loop should look like this:

  for (i = 0; i < n; ++i)
      for (j = i + 1; j < n; ++j)
Re:CoffeePhysics: A JS/CS Physics Engine by dmvaldman on Wednesday February 29, 2012 @11:24AM (#3648382)
That's N*(N+1)/2 steps, or order N^2. Best to visualize as the number of entries on the upper triangle of an NxN matrix.
Re:CoffeePhysics: A JS/CS Physics Engine by HardyLeung on Wednesday February 29, 2012 @12:47PM (#3648807)
I think you need to revisit your understand of complexity. It is O(N^2). If you want the exact count, it is N(N-1)/2. N! is an exceedingly large number even for very small N.
Re:CoffeePhysics: A JS/CS Physics Engine by nlogn on Wednesday February 29, 2012 @09:58PM (#3650736)
Yep I'm wrong. Mixed up factorial just like mistercow said. Thanks for the corrections. And here I was worrying that someone would complain that my loop wouldn't address the issues of collision response necessitating more checks, thus making a recursive solution necessary.
Re:CoffeePhysics: A JS/CS Physics Engine by mistercow on Wednesday February 29, 2012 @01:03PM (#3648887)
That's not N! . N! is (N)(N-1)(N-2)... What you have there is (N)+(N-1)+(N-2)..., which is O(N²)