Neighbor iteration is implemented by scanning all E edge records once per vertex — what does that cost?

## What the code actually does An edge list stores edges as flat records — a source, a target, maybe a weight — with no per-vertex index. Code that needs "the edges leaving s" therefore has only one option available in the data it was handed: filter the whole collection. Written once, that is a defensible O(E) operation. Written inside a loop over vertices, it becomes O(V*E), and the multiplication is invisible at a glance because each half looks reasonable on its own. This is the review pattern worth training your eye on: a linear helper called a linear number of times. The helper's own bound is honest, the enclosing loop's bound is honest, and the product is the defect. ## Putting numbers on the blowup O(V*E) is not a mild penalty. For a graph with V = 10^5 and E = 10^6, a single sweep is 10^11 record comparisons — minutes to hours, where the indexed version finishes in the time it takes to touch 1.1*10^6 entries. The scaling is worse than it first appears, because on real data E grows with V. If the graph is sparse with E proportional to V, the sweep is effectively O(V^2). If the graph is dense with E proportional to V^2, it is O(V^3). This is also why the bug survives code review and testing. On a fixture graph with 50 vertices and 200 edges, V*E is 10,000 — instant. Nothing in the test suite distinguishes the two implementations; only production scale does. ## The fix: build the index once The repair is a counting pass, and it is worth being able to describe it precisely rather than gesturing at "just use an adjacency list": 1. **Count.** Walk the E records once, incrementing `outdeg[from]` for each. O(E). 2. **Prefix-sum.** Turn those counts into start offsets: `start[0] = 0`, and `start[i] = start[i-1] + outdeg[i-1]`. O(V). 3. **Place.** Walk the records once more, writing each target into the next free slot of its source's region and advancing a per-vertex cursor. O(E). The result is one contiguous array of neighbor entries plus a V+1-element offset array. Vertex s's neighbors occupy positions `start[s]` through `start[s+1] - 1`, so enumerating them is O(deg(s)) and the whole sweep over every vertex touches each edge exactly once: O(V+E). Total build cost O(V+E) time, O(V+E) memory. Since the sweep alone was O(V*E), the index pays for itself the first time you run it — you do not need to amortise it over many queries to justify it. The contiguous layout is a second, non-asymptotic win: neighbor entries for one vertex sit next to each other in memory, so the walk streams instead of chasing scattered references. ## Alternatives, and why they are usually worse here **Sort the records by source.** O(E log E), after which each vertex's edges form one contiguous run and a merged sweep is O(E). Correct and simple, but strictly more work than the O(E) counting build, and it mutates or copies the input. **Convert to a matrix.** That drops the sweep to O(V^2), which beats O(V*E) whenever E exceeds V, but it costs V^2 memory and is still asymptotically worse than O(V+E) on a sparse graph. Reaching for the matrix to fix a scan problem is the classic over-correction: it trades a time bug for a memory bug. **Cache the last scanned position.** Tempting and wrong, because the records are unordered — the edges leaving vertex 7 are scattered arbitrarily, so there is no position to resume from. This distractor is common precisely because it feels like a cheap fix. ## When the edge list is the right storage None of this means edge lists are bad. They are the smallest representation, O(E) with no per-vertex overhead, and they are exactly right for workloads that consume every edge in some order and never ask about one vertex: sorting all edges by weight, streaming them from storage in batches, or algorithms whose inner step relaxes or examines every edge each round. The defect is not the storage choice; it is *querying by vertex against a representation that has no vertex index*. Either build the index or stop asking per-vertex questions. ## What to say in the review Name the cost as a product, not as a bound on one loop: "this is V passes over E records, so O(V*E) — at our scale that's 10^11 comparisons." Then propose the concrete replacement — the counting build above, one time, in O(V+E) — and note that the fixture graphs in the test suite are far too small to show the difference, so the change needs a benchmark at a realistic size rather than a green test run.