5 ms·

Barnes-Hut is O(n log n) http://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation http://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation

• acadien 13y ago
  Yes, once you start cutting off long range effects you can improve on the strict O(N^2) limitations.
  • cscheid 13y ago
    It's not cutting off. It's replacing many long-range effects with a single one weighted more (and done it carefully so that the floating-point error is literally smaller than you could tell). There's even better methods that take O(n) time, like the fast multipole expansion ones.
    • darkmighty 13y ago
      Btw this goes into numerical analysis, and O(-) is important but so is error convergence. I imagine these big-O figures are for a constant error, but I figure the asymptotic may change behavior as the other parameter changes.
  • ngoldbaum 13y ago
    One could also use FFTs and the particle-mesh method or a TreePM method. Basically, the particle masses are deposited on a fine mesh. Poisson's equation gets solved using FFTs and then the particle accelerations are computed by interpolating on the gradient of the potential field.