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)

Memory usage in graph representations varies with how edges are stored. An adjacency matrix reserves a cell for every pair of vertices, so you always allocate V × V slots. That makes the space complexity O(V^2) no matter how many edges exist, which becomes wasteful for very sparse graphs where E is much smaller than V^2.

Other representations scale with the number of edges. An adjacency list stores each edge once (plus the vertex headers), giving O(V + E) space, which is much smaller when the graph is sparse. An edge list uses O(E) space, also efficient for sparse graphs. An incidence matrix connects vertices to edges and tends to require O(VE) space, which can be large as well.