N-body physics is O(n^2), each body has (n-1) interactions to compute, so it would be O(n*n). That being said, I've found a paper which gives an algorithm for implementing N-body physics in something like O(n log n) or O(n).
http://www.cs.hut.fi/~ctl/NBody.pdf