A common algorithm used in N-body gravitational calculations with large numbers of bodies (stars in a galaxy, galaxies in the universe, etc.) is the Barnes-Hut algorithm, which assembles particles into an octree for approximate bulk calculations of gravitational forces between distant areas. The complexity of this algorithm is O(N log N), compared to the O(N^2) of a more realistic direct calculation between all pairs of points.
I’m trying to fully understand where the N log N comes from. I understand that, once the octree is assembled, the calculation of forces is N log N because you have to go through each particle (N), and each particle “sees” approximately log N other particles because of the octree reducing the number of calculations needing to be performed for distant particles.
What I’m still trying to understand is what the complexity is for assembling the octree in the first place. Is it also N log N? N because you need to do it for each particle, and log N because that’s approximately how deep you’ll have to go (with some factor in front) to reach an isolated leaf in the tree?