Which representation uses O(V+E) space, and which uses O(V^2) space?

Which representation uses O(V+E) space, and which uses O(V^2) space?

• A. Adjacency list uses O(V^2) space; Adjacency matrix uses O(V+E) space.
• B. Both representations use O(V^2) space.
• C. Adjacency matrix uses O(V+E) space; Adjacency list uses O(V^2) space.
• D. Adjacency list uses O(V+E) space; Adjacency matrix uses O(V^2) space.

Answer: (D)

The question tests how graph representations use memory. An adjacency list stores, for each vertex, a list of its neighbors, so total storage grows with the number of vertices plus the number of edges. In big-O terms this is O(V + E). An adjacency matrix, on the other hand, allocates a full V by V grid to indicate whether each possible pair of vertices is connected, so the space is O(V^2) regardless of how many edges actually exist. Therefore, the adjacency list uses O(V + E) space, while the adjacency matrix uses O(V^2) space.

The question tests how graph representations use memory. An adjacency list stores, for each vertex, a list of its neighbors, so total storage grows with the number of vertices plus the number of edges. In big-O terms this is O(V + E). An adjacency matrix, on the other hand, allocates a full V by V grid to indicate whether each possible pair of vertices is connected, so the space is O(V^2) regardless of how many edges actually exist. Therefore, the adjacency list uses O(V + E) space, while the adjacency matrix uses O(V^2) space.