I had software (freeware that models two galaxies interacting. Google is your friend - there are a handful of interesting (but limited) programs out there.
The number of calculations depend on your algorithim but are order n cubed for a very unsophisticated approach (calculate acceleration and speed in x,y,z (6 operations) for every body interacting with every other body. Half that if you're clever as the forces between every two bodies are equal so 1/2 * 6 * (3 position + 3 acceleration) = 0rder 3 n^3
http://www.synthetic-reality.com/galaxy.htm
An n-tree alogrithim of greater sophistication might manage order n squared * log n without losing accuracy - which is quite an accomplishment. Better still if such a program is well written to use a modern computers CPU and GPU - you can probably manage simultaion between 50,00 to 100,000 stars in real time!
http://www.cs.princeton.edu/courses/...arnes-hut.html