No. Collision detection is not always O(N^2).
For instance, say we have a 100x100 space with objects with size 10x10. We could divide this space in cells of 10x10 with a grid.
Each object can be in up to 4 grid cells (it could fit right in a block or be "between" cells). We could keep a list of objects in each cell.
We only need to check for collisions in those cells. If there is a maximum number of objects per grid cell (say, there are never more than 4 objects in the same block), then collision detection for each object is O(1) and collision detection for all objects is O(N).
This is not the only way to avoid O(N^2) complexity. There are other methods, more adequate for other use-cases - often using tree-based data structures.
The algorithm I described is one type of Space partitioning, but there are other space partitioning algorithms. See Types of space partitioning data structures for some more algorithms that avoid the O(N^2) temporal complexity.
Both Box2D and Bullet support mechanisms to reduce the number of checked pairs.
From the manual, section 4.15:
Collision processing in a physics step can be divided into
narrow-phase and broad-phase. In the narrow-phase we compute contact
points between pairs of shapes. Imagine we have N shapes. Using brute
force, we would need to perform the narrow-phase for N*N/2 pairs.
The b2BroadPhase class reduces this load by using a dynamic tree for
pair management. This greatly reduces the number of narrow-phase
calls.
Normally you do not interact with the broad-phase directly. Instead,
Box2D creates and manages a broad-phase internally. Also, b2BroadPhase
is designed with Box2D’s simulation loop in mind, so it is likely not
suited for other use cases.
From the Bullet Wiki:
There are various kinds of broadphase algorithms that improve upon the
naive O(n^2) algorithm that just returns the complete list of pairs.
These optimised broadphases sometimes introduce even more
non-colliding pairs but this is offset by their generally improved
execution time. They have different performance characteristics and
none outperform the others in all situations.
Dynamic AABB Tree
This is implemented by the btDbvtBroadphase in Bullet.
As the name suggests, this is a dynamic AABB tree. One useful feature
of this broadphase is that the structure adapts dynamically to the
dimensions of the world and its contents. It is very well optimized
and a very good general purpose broadphase. It handles dynamic worlds
where many objects are in motion, and object addition and removal is
faster than SAP.
Sweep and Prune (SAP)
In Bullet, this is the AxisSweep range of classes. This is also a good
general purpose broadphase, with a limitation that it requires a fixed
world size, known in advance. This broadphase has the best performance
for typical dynamics worlds, where most objects have little or no
motion. Both btAxisSweep3 and bt32AxisSweep3 quantize the begin and
end points for each axis as integers instead of floating point
numbers, to improve performance.
The following link is a general introduction to broadphase and also a
description of the Sweep and Prune algorithm (although it calls it
"Sort and Sweep"):
http://www.ziggyware.com/readarticle.php?article_id=128
Also, take a look at the wikipedia page:
http://en.wikipedia.org/wiki/Sweep_and_prune