Which graph representation has a space complexity of O(V^2) regardless of the number of edges, making it inefficient for very sparse graphs?

Which graph representation has a space complexity of O(V^2) regardless of the number of edges, making it inefficient for very sparse graphs?

• A. Adjacency list
• B. Edge list
• C. Adjacency matrix
• D. Incidence matrix

Answer: (C)

Evaluating graph representations by memory usage shows why the adjacency matrix stands out here. An adjacency matrix keeps a table with a row for every vertex and a column for every vertex, so you end up with V by V cells. Each cell simply records whether there is an edge between that pair of vertices. Because you allocate space for every possible pair, the total memory grows with V^2 and does not depend on how many actual edges exist. That means it’s O(V^2) regardless of E, which becomes highly inefficient for very sparse graphs where E is much smaller than V^2. Other representations store only the actual edges (or a combination of vertices and edges), so their memory scales with E (or V+E), making them far more space-efficient when the graph is sparse.

Evaluating graph representations by memory usage shows why the adjacency matrix stands out here. An adjacency matrix keeps a table with a row for every vertex and a column for every vertex, so you end up with V by V cells. Each cell simply records whether there is an edge between that pair of vertices. Because you allocate space for every possible pair, the total memory grows with V^2 and does not depend on how many actual edges exist. That means it’s O(V^2) regardless of E, which becomes highly inefficient for very sparse graphs where E is much smaller than V^2. Other representations store only the actual edges (or a combination of vertices and edges), so their memory scales with E (or V+E), making them far more space-efficient when the graph is sparse.