Practice question · Multiple choice
Why does allocating an adjacency matrix for a sparse network of one million members cause a critical memory issue?
Hints
- Compute the matrix size for a million vertices, then count how many cells hold a 1.
- The lists save all that space. What do they give up in exchange?
Show the answer
C. Because the matrix needs a trillion cells, almost all of them zero.
Why
The arithmetic settles it: 10¹² cells to record a few hundred million edges, about 0.03% non-zero. Lists store only what exists, which for a sparse graph is the difference between infeasible and routine. The cost is real, 'are A and B connected?' becomes a scan of A's list, so density decides, and real-world networks are almost always sparse.
Practise Graph Representations
The app has 7 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.