What is the space complexity of a graph represented as an adjacency list with V vertices and E edges?
Show answer
Θ(V + E)
Adjacency lists are more space-efficient than adjacency matrices (which use Θ(V²) space) for sparse graphs, as they only store the edges that actually exist.
Also asked as:
- For a graph with V vertices and E edges, what is the Big Theta space complexity when using an adjacency list representation?