13

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.

0

2 Answers 2

18

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.

1
  • O(V + E) = O(max(V, E)) because if E > V, since O is an upper bound, we are allowed to "round up" V and say this: O(V + E) = O(E + E). This yields O(2E), resulting in O(E). Swap the variables if V > E, and it should be evident why O(V + E) = O(max(V, E)). I find the former's syntax easier to parse, and the latter's semantics easier to understand. Commented Jan 9, 2016 at 10:55
0

I think you can think of it in this way, if you have 10 vertexes and 30 edges, then let v and E stand for the storage you need for storing each vertex and edge.

10(V+E)<=(10V+30E)<=30(V+E)

Based on the above equation, you can conclude it requires Ѳ(V+E) space.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.