Course contentsShow
← Computer Science
Lesson 671 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Adjacency Matrix: Space-Time Tradeoffs

Understand when adjacency matrices are optimal for dense graphs despite O(V²) space usage.

Adjacency Matrix: Space-Time Tradeoffs

You'll learn when the O(V²) space cost of adjacency matrices is actually worth it.

The Core Tradeoff

An adjacency matrix always uses O(V²) space—you create a full V×V grid regardless of how many edges exist. This seems wasteful, but there's a payoff: many operations become blazingly fast.

The key insight: dense graphs (where most possible edges exist) make this tradeoff favorable. If you have a graph with V vertices and close to V² edges, you're using that matrix efficiently. Each cell holds meaningful data, not just empty space.

When Adjacency Matrices Win

Consider checking if edge (u, v) exists: with an adjacency matrix, it's O(1)—just look at matrix[u][v]. Adding or removing edges? Also O(1). Need to check all neighbors of a vertex? O(V), because you scan that vertex's row.

For sparse graphs (few edges), you're paying for V² storage but only using a fraction of it. A graph with 1000 vertices but only 2000 edges wastes most of the matrix.

The Decision Point

Use adjacency matrices when:

  • Your graph is dense (edges approach V² in number)
  • You need frequent edge lookups (is there an edge from A to B?)
  • You're implementing algorithms that check many potential edges
  • Space is acceptable given your vertex count

Think of it like buying a parking garage: if you expect it mostly full (dense), the space-per-spot makes sense. If it's usually empty (sparse), you've paid for concrete you don't need.

Key Takeaway: Adjacency matrices trade O(V²) space for O(1) edge operations—optimal for dense graphs where most connections exist and fast lookups matter more than memory efficiency.