In an adjacency list, matrix and edge list, what does testing whether edge u->v exists cost?

## The query "Is there an edge u->v?" — sometimes called the adjacency test — is one of the two primitive graph queries, the other being "enumerate u's neighbors". A representation is fast at one, slow at the other, or expensive in space; no layout is best at everything. Make the workload concrete: a route dataset of weighted directed records shaped `{from, to, price}`, meaning a direct hop from one airport to another at a given fare. The system must answer *is there a direct hop u->v, and what does it cost?* ## Matrix: O(1), paid for in advance Cell `[u][v]` holds the price or a sentinel for "no edge". One index computation, one read, done — O(1) worst case, no scanning, no hashing, cache-friendly if you repeatedly probe within a row. The cost was paid at allocation: V^2 cells regardless of how many hops actually exist. For a few thousand airports that is millions of cells and entirely reasonable. For millions of vertices it is unavailable, which is why "the matrix is O(1) so use the matrix" is only half an answer — the other half is whether V^2 fits. ## Adjacency list: O(deg(u)), and the degree distribution matters Slot u holds u's outgoing (neighbor, price) pairs. Testing for v means scanning that sequence: O(deg(u)) comparisons, stopping early on a hit. For a vertex with twelve outbound routes this is trivially fast — often faster in wall-clock terms than a cache-missing probe into a huge matrix. The trap is that deg(u) is not uniform. Real graphs are heavy-tailed: a handful of hub vertices carry a large share of the edges. If your test loop happens to hammer the hubs, the "cheap" O(deg(u)) test is a scan of thousands of entries. Quote the bound as O(deg(u)), never as O(1), and say which u you mean. Keeping each vertex's neighbors sorted lets you binary search within the slot for O(log deg(u)), at the price of ordered insertion. Keeping them in a per-vertex hash-based set gives expected O(1) — worst case still linear under collisions — at the price of extra memory per vertex and the loss of any deterministic neighbor order, which matters when you need reproducible traversal output. ## Edge list: O(E) unless you build an index A flat collection of records has no per-vertex structure at all, so the only honest answer is a linear scan: O(E) per query, half a million comparisons for half a million routes. One query is fine. A query inside a loop is a disaster, and that is exactly how edge-list code gets slow. Two cheap upgrades exist. Sort the records once by (from, to) — O(E log E) — and every later test is an O(log E) binary search; the catch is that inserting a new route into a sorted array is O(E), so this suits a dataset that is loaded and then read. Or hash the (from, to) pairs into a set for expected O(1) lookups, which handles inserts fine but costs memory proportional to E and answers only the existence question, not the neighbor-enumeration one. ## Summary of the tradeoff | representation | edge test | enumerate u's neighbors | space | |---|---|---|---| | matrix | O(1) | O(V) | O(V^2) | | adjacency list | O(deg(u)) | O(deg(u)) | O(V+E) | | edge list | O(E) | O(E) | O(E) | | edge list sorted by (from, to) | O(log E) | O(log E + deg(u)) | O(E) | Notice the matrix's O(1) test comes bundled with an O(V) neighbor walk: to list the routes out of one airport you scan a whole row, mostly empty cells. Traversal algorithms enumerate neighbors constantly and test individual pairs rarely, which is why they are almost always written against adjacency lists even though the matrix wins the headline query. ## Directed and undirected Everything above is stated for a directed edge u->v, which is what route data is: a hop u->v at one price says nothing about v->u. For an undirected graph the matrix is symmetric, so you can store only one triangle and halve the memory; the adjacency list stores each edge twice, once in each endpoint's slot, so E edges become 2E entries. The undirected adjacency test also gains a small optimisation — check whichever endpoint has the smaller degree, since both slots must agree. The answer an interviewer wants is not three memorised bounds but the reasoning that produces them: what index does this layout maintain, and what must be scanned when the index does not cover the query?