The second algorithm you are thinking of is probably what is known as "sort-and-sweep". Basically each object takes up an interval along each axis, so a necessary condition for collisions between two objects is that the intersection of the intervals along each axis are non-empty. (which means if there is no overlap of intervals along any axis, you can guarantee they are not colliding).

You compute the bounds along each axis in linear time. The sorting of these bounds can be done in linear time, then you take a pass over each axis looking at the marked intervals, which is also linear.