How is the memory required for adjacency list representation is O(V+E)?

Question

How is this statement valid?

"For both directed and undirected graphs, the adjacency-list representation has the desirable property that the amount of memory it requires is O(V+E)."

source: introduction to algorithms, cormen.

Answer 1

Let's assume that you are storing adjacency lists in an array, i.e.

edges[v] represents a list of edges outgoing from v

In order to measure the space complexity, firstly just notice that you have exactly V records in the array, one for each vertex. So you are using O(V) memory for just storing the empty lists.

Next, notice that if the graph is directed, every edge appears exactly once in the array of those lists.

If the graph is undirected, every edge appears exactly twice in the array of those lists.

In both cases, the number of entries in the whole array is bounded by at most 2 * E = O(E).

Putting it together, we see that the total number of memory is bounded by O(V + E) which is the same as O(max(V, E)).

The term V surpasses E if and only if the graph is a set of disjoint trees which is called a forrest.