I'm writing an article on the n-body problem, and I'd like to be technically accurate.
The code is here. And here are the comments and loops:
/**
* Given N bodies with mass, in a 3d space, calculate the forces of gravity to be applied to each body.
*
* This function is exported to JavaScript, so only takes/returns numbers and arrays.
* For N bodies, pass and array of 4N values (x,y,z,mass) and expect a 3N array of forces (x,y,z)
* Those forcess can be applied to the bodies mass to update the its position in the simulation.
* Calculate the 3-vector each unique pair of bodies applies to each other.
*
* 0 1 2 3 4 5
* 0 x x x x x
* 1 x x x x
* 2 x x x
* 3 x x
* 4 x
* 5
*
* Sum those forces together into an array of 3-vector x,y,z forces
*
* Return 0 on success
*/
// For all bodies:
for (let i: i32 = 0; i < numBodies; i++) { // TypeScript. i32 is type 32bit int
// Given body i: pair with every body[j] where j > i
for (let j: i32 = i + 1; j < numBodies; j++) { // is this "n" or "log n"?
// Calculate the force the bodies apply to one another
stuff = stuff
}
}
return stuff
I'm fairly certain the algorithm is > O(n) and <= O(n*n).
By process of elimination that leaves O(n log n) as the other option.
Looking at the grid, I think O(1/2 n^2) = O(n^2)
Looking at the loops, I think the inner loop is < n, but I'm not sure if it's all the way to log n.
If I'm looping through n, what does adding a log n inner loop look like? If not an inner loop, an outer loop?
