It looks like there's some sort of gravity involved. So then how do you get around the O(n^2) problem of comparing the contribution of each particle to every other particle? Did they implement an quadtree of some sort, or is it something else?

It looks like it's using a fluid solver. So, it's not that every particle is interacting with every other particle, but that there's a flow vector being established at each point on the screen and that's being added to each particle's position.

Disclaimer: I haven't actually analyzed the source.

I'm wondering what optimization you can to that do with a quadtree. The only way I can see is if you sacrifice accuracy on distant particles by quantizing and counting. You could use geometric hashing to do the same thing.

Anyway, I don't think this demo is exhibiting inter-particle attraction, but I'm not positive.

Exactly right. The most common scheme uses a quadtree and runs around O(n log n).

http://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation