The collision interest matrix of Garcia-Alonso [GASF94] and
spatial division, allow the number of objects that need to be tested against
each other to be reduced from the worst case 
for n objects. Bounding
volumes can be used to speed up collision detection because they reduce the
average time complexity of each collision test --- if the objects' bounding
volumes don't intersect (a simple test to carry out), then an expensive
collision test can be avoided.
Other techniques work in a similar vein by reducing the average time complexity required for each collision test, and are often tied into the type of representation being used to model the objects.
When objects collide, it is the case that the relative motion of the objects is towards each other. Thus, generally speaking, objects that are moving away from each other, cannot collide and don't need to be tested. This criteria is also useful in differentiating between objects that are colliding, and ones that have been in contact and are beginning to separate. Vanecek [Van] applied this concept to individual faces of polyhedra, and so reduced the number of polygons (usually by half) that needed to be compared when checking for interpenetration between polyhedra.
Baraff [Bar90] noted that the geometric relationships between the objects in his simulation didn't change much between successive time steps, and so employed a method which took advantage of this coherence. The objects in the simulation were restricted to unions of convex polyhedra and convex closed surfaces. Because of this restriction, two objects did not penetrate if and only if a separating plane existed between the two. Baraff called the separating plane a witness --- it bore witness to the fact that the two objects didn't interpenetrate, and because of the time coherence in the geometry of the objects in the simulator, could be used in successive time steps to quickly show that two objects didn't interpenetrate.
In simulations where objects are modelled using polygons, the test for interpenetration between objects can be very expensive as the objects can be made up of a large number of polygons which need to be tested against each other. Vanecek's technique mentioned above, is one way of reducing the number of polygons that need to be checked, while other methods used involved applying spatial division and hierarchical structures to individual objects to order the polygons [MW88,GASF94,BV93,VT94].