Summary of what's below: The type of simulations described in the article do not scale like O(N^2) but more like O(N log N).
A small correction here.. The gravitational force calculation for N-body simulations are only O(N^2) if they're done using direct summation and force calculation. That's only necessary if you care about the motions of individual stars. The largest simulations I'm aware of that do that use a few 10s or 100s of millions of stars. They're typically used for studying individual star clusters, the regions around supermassive black holes, and perhaps dwarf galaxies. But the simulation in this article/press release has a few 10s of billions of particles, I believe. And those particles are all much more massive than individual stars. So while there are "star particles" in the simulations, it's more accurate to think of them as a set of particles which constitute a monte carlo sampling of the stellar mass distribution.
One aspect of that is you now no longer care about the detailed trajectories of individual particles[0], instead caring about the overall representation of the mass distribution. So you don't need as high of accuracy in the force calculation. Going back to the 1980's, people have been using numerical tricks to reduce the scaling of the simulations with the particle number. This includes algorithms such as treecodes, particle-mesh codes, etc., which reduce the scaling to O(N log N) or even O(N). These are sufficient to run simulations of describing the overall gravitational field.
The scaling for hydro codes is probably more complicated, particularly for simulations which use a moving mesh.
There's a nice summary of numerical techniques for this type of work here: http://arxiv.org/abs/1412.5187
[0] One can determine if interactions between individual stars is important to a system's evolution by comparing the 2-body relaxation time to the age of the system. This is discussed on pages 8–9 of the preprint linked above.
Also, for everyone to enjoy simulations results, check the simulations by Canup from the giant impact hypothesis[2]. Another thing to consider, the supercomputer used for this specific simulation had about the same computer power as a high end GPU from today.
[0] https://benedikt-bitterli.me/bbw.html
[1] http://lasp.colorado.edu/~espoclass/ASTR_5835_2013_Files/201...
It's not so much a novelty as it is pushing the envelope.
The main problem with these kind of simulations is that they're O(N^2). You can't get away with modelling each star, you have to model the interaction of each star with every other star.
And then add in interstellar dust, which has non-neglible mass. And then run the simulation for 8 billion years.
There are naturally some optimizations and short-cuts to be made. :)