# bullet-0003: O(P²) pair removal — `findLinearSearch` in `btSortedOverlappingPairCache`

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — Insufficient Control of Quadratic Complexity)
**Target:** bulletphysics/bullet3
**File:** `src/BulletCollision/BroadphaseCollision/btOverlappingPairCache.cpp`
**Lines:** 450, 494
**Status:** PATCHED (migration to btHashedOverlappingPairCache recommended)

## Description

`btSortedOverlappingPairCache::removeOverlappingPair` and `findPair` scan the
pair array linearly:

```cpp
// btOverlappingPairCache.cpp:450
int findIndex = m_overlappingPairArray.findLinearSearch(findPair);  // O(P)
```

```cpp
// btOverlappingPairCache.cpp:484–487 (developer comment)
///this findPair becomes really slow. Either sort the list to speedup the query, or
///use a different solution. It is mainly used for Removing overlapping pairs.
///we could keep a linked list in each proxy, and store pair in one of the proxies
```

With P pairs, removing all pairs is O(P²). The developer comment acknowledges the
defect and even proposes a fix (linked list per proxy). The same linear scan
appears in `findPair` (line 494).

Real-world impact: a scene with 10 000 overlapping pairs (dense crowd or particle
system) requires 50 million comparisons to clear the pair cache on scene reset or
mass body deletion.

Note: `btHashedOverlappingPairCache` (the other implementation in the same file)
already uses a hash table for O(1) pair lookup. `btSortedOverlappingPairCache`
is the legacy path that should be avoided for dynamic worlds.

## Root Cause

`m_overlappingPairArray` is a `btAlignedObjectArray<btBroadphasePair>` with no
index structure. Pair lookup requires a full linear scan.

## Fix

Option 1 (preferred): Stop using `btSortedOverlappingPairCache` for dynamic worlds.
`btDbvtBroadphase` (the recommended broadphase) already creates
`btHashedOverlappingPairCache` by default — O(1) add/remove/find.

Option 2 (in-place): Add a `btHashMap<btBroadphasePairSortPredicate, int>`
index alongside `m_overlappingPairArray`, mirroring the approach already used
in `btHashedOverlappingPairCache`.

**Patch:** `patch/bullet-0003-sortedpairscache-use-hashed-cache.patch`

## Complexity

| Scenario | Before | After |
|----------|--------|-------|
| Remove P pairs from sorted cache | O(P²) | O(P) |
| P=500 pair removal | ~125 000 comparisons | ~500 ops |
| P=10 000 pair removal | ~50 000 000 comparisons | ~10 000 ops |
| Speedup at P=500 | — | ~250x |
| Speedup at P=10 000 | — | ~5 000x |

## Unit Test

`unit/BulletAlgorithm.java` — see bullet-0003 section.
Correctness: both paths produce empty array after removing all pairs.
Performance: op-count ratio >= 5x verified at P=500 (measured 126x).

Run:
```
javac -d /tmp/out defects/bullet/unit/BulletAlgorithm.java
java -cp /tmp/out unit.BulletAlgorithm
```
Output: `6/6 PASS`
