Why does an adjacency matrix use O(V^2) space while an adjacency list uses O(V+E)?
answer
- count the cells you reserve, not the edges
- matrix size is fixed once V is known
- list holds one entry per existing edge
- 10^7 vertices squared is 10^14 cells
- sparse means E far below V^2
basics
~20 sAn adjacency matrix reserves a cell for every pair of vertices, so its size depends only on V, never on the edge count. An adjacency list stores one entry per vertex plus one per actual edge, so it grows with E.
solid answer
~40 sThe matrix is a V-by-V grid: every ordered pair gets a cell whether or not the edge exists, so the footprint is fixed the moment you know V. The list keeps, for each vertex, a sequence of its neighbors — V headers plus one entry per edge, hence O(V+E). The gap only matters when the graph is sparse, and real relationship graphs almost always are. Take a follows graph with 10^7 accounts averaging 200 outgoing follows: that is about 2*10^9 edges, so the list needs single-digit tens of gigabytes, while the matrix needs 10^14 cells — roughly 12 terabytes even at one bit per cell. When E is close to V^2 the two converge and the choice turns on constants instead.
go deeper
Be ready to state both bounds and say plainly why the matrix's does not depend on the edge count. Knowing that most real graphs are sparse, and that sparse means E is far below V^2, is the whole expected answer.
Explain the layouts, not just the bounds: a V-by-V grid allocated up front versus a per-vertex sequence of neighbors, and what each one costs to walk. Turn the asymptotics into actual bytes for a stated V.
Show that you check affordability before elegance — compute V^2 for the real V, then pick by workload. Mention that O(V+E) counts entries, and that a contiguous index-plus-offsets layout beats scattered per-vertex containers at the same bound.
Own the framing that the representation is a long-lived decision the rest of the system inherits: it fixes memory per machine, whether the graph fits in one process, and what every later algorithm can cost. Be able to say what changes at ten times the vertex count.
## The two layouts A graph is a set of V vertices and E edges. Every representation answers the same questions — *does edge u->v exist?* and *who are u's neighbors?* — but stores different things to do it. **Adjacency matrix.** Number the vertices 0..V-1 and allocate a V-by-V grid. Cell `[u][v]` holds whether the edge u->v exists (or its weight, or a sentinel meaning "absent"). The grid is allocated in full before a single edge is inserted, so the footprint is a function of V alone. Adding a million edges to a matrix that already exists changes nothing about its size; removing every edge changes nothing either. That is the whole reason the bound is written O(V^2) and not O(V^2 + E) or O(E). **Adjacency list.** Keep an array indexed by vertex; slot u holds a sequence of the vertices u points to. You store V slots plus exactly one entry per edge — O(V+E). Nothing is reserved for edges that do not exist. **Edge list.** Store the edges as a flat collection of (from, to) records and nothing else — O(E), with no per-vertex index at all. ## Sparse and dense "Sparse" means E is far below V^2 — usually E is closer to a constant multiple of V. "Dense" means E is a meaningful fraction of V^2. The distinction is not decoration; it is what makes the O(V^2) versus O(V+E) comparison meaningful: | | matrix | adjacency list | edge list | |---|---|---|---| | space | O(V^2) | O(V+E) | O(E) | | iterate u's neighbors | O(V) | O(deg(u)) | O(E) | | grows when edges are added | no | yes | yes | On a sparse graph, O(V^2) is catastrophically larger than O(V+E), and iterating a vertex's neighbors from a matrix means walking a whole row of V cells to find the handful that are set. ## Put real numbers on it Asymptotic notation is a scaling claim, not a number of bytes; the interview answer that lands is the one that converts. A social follows graph with V = 10^7 accounts, each following about 200 others, has E of roughly 2*10^9 directed edges. - Adjacency list: about 2*10^9 neighbor entries. At 4 bytes per vertex id that is around 8 GB of edge data plus an index of 10^7 slots. Large, but it fits on one well-provisioned machine. - Adjacency matrix: 10^7 * 10^7 = 10^14 cells. Even packed at one bit per cell that is 10^14 bits, about 12.5 terabytes — and one byte per cell would be 100 TB. It is not a tuning problem; the representation is simply unavailable. That conversion is also what disarms the most common wrong answer: "the matrix gives O(1) edge lookup, so it's better." The lookup really is O(1), but you cannot buy it here at any price. ## What O(V+E) hides Be honest about the list's constants too. O(V+E) counts *entries*, not bytes. A list built from per-vertex containers pays a header per vertex, capacity slack inside each container, and scattered memory that defeats prefetching — a neighbor walk can miss cache on nearly every step. A flat, index-plus-offsets layout (all neighbor entries in one contiguous array, with a per-vertex start offset) keeps the same O(V+E) bound with far better locality, which is why serious graph code usually builds one. Asymptotics pick the representation; layout decides whether it is fast. ## Choosing Ask two questions. First, is V^2 memory affordable at all? For V in the low thousands, V^2 is millions of cells — fine. For V in the millions it is out of reach, and the decision is made for you. Second, what does the workload do most: test individual pairs, or walk neighbor sets? Pair tests favour the matrix; traversal favours the list. Sparse graphs with traversal-heavy workloads — which is most real-world graph work — take the adjacency list, and that is the default you should be able to justify in one breath rather than recite.
- What does an edge list cost, and when is that enough?An edge list stores the edges as flat (from, to) records with no per-vertex index, so it is O(E) space — smaller than either alternative. It is enough when the workload only ever sweeps every edge, for example sorting all edges by weight or streaming them from storage. The moment you need "who are u's neighbors", it costs a full O(E) scan per query, which is why most code converts it to an adjacency list once up front.
- Does O(V+E) mean the adjacency list is always the cheaper one in bytes?No — O(V+E) counts entries, not bytes. A list built from one container per vertex pays a header and spare capacity for each of the V slots plus per-entry overhead, so a graph with almost no edges can still cost more than a tiny packed matrix. For small V the matrix can genuinely be smaller and faster; the asymptotic gap only takes over once V is large and E stays well under V^2.
- How does storing weights change the picture?Both representations hold weights fine. The matrix stores the weight in the cell instead of a flag, which usually widens each cell from one bit to four or eight bytes and multiplies the V^2 footprint accordingly. The adjacency list stores (neighbor, weight) pairs, adding a constant per edge and leaving the O(V+E) bound unchanged. Weights therefore hurt the matrix far more than the list.
The matrix is a seating chart with a chair printed for every pair of guests before anyone arrives; the list is a guest book where you write down only the pairs who actually met.
saying these in an interview costs you the question
- Thinks the matrix only stores the edges that exist
- Says adjacency lists waste more memory because of the extra containers
- Quotes O(V^2) without converting it to bytes for the given V
- Claims the two representations cost about the same on a sparse graph
- Believes only one of the two can store edge weights