Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Adjacency list — where it appears

A graph stored as a list of neighbours per vertex, cheap in space and a pointer chase to traverse. It is cheap in space and a pointer chase to traverse, so it wins on one count and loses badly on the other.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

with the edge — connected01234567all 8 edges presentwithout it — two components01234567one edge withheld, everything else identicalV = 8, E = 8Ω(E), by adversary rather than by counting

The adversary who hides the edge

The floor under comparison sorting comes from counting outputs — n! of them, so log₂(n!) comparisons. Connectivity has two outputs, so the same argument gives a floor of one comparison, which is useless. A different kind of argument gives Ω(E), and having both on the site is the point: lower bounds are not one technique.

floors · Floor 10³10³10⁴Vmodelled missesadjacency listCSR array96% miss27% miss64 lines × 8 elements, fully associative, LRU3.6× between two layouts of one graph

A list and a block of memory

The same traversal, over the same graph, examining the same edges in the same order, laid out two ways. Twelve thousand two hundred and eighty-eight edge slots either way; 11,812 modelled cache misses against 3,258. This is the site's largest gap between two counts of one run, and it exists because one of the layouts is a pointer chase and the other is a sweep.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

AdjacencyTraversalAdversary argumentCacheConnectivityCSR (compressed sparse row)Decision treeDistributionEvasivenessLocalityLower boundMemory layout

All concepts