Do edge lists have O(E) storage if default values are used for absent keys?

Question

Ordinarily, edge list representations of graphs take $O(V+E)$ space, where $V$ is the number of vertices and $E$ is the number of edges. For example, consider a graph with 5 nodes and a single edge from node 0 to node 1. The edge list, represented as a Python dictionary, would be:

edges = {0: [1], 1: [], 2: [], 3: [], 4: []}

An alternative (for sparse graphs) would be to have keys only for nodes with outgoing edges. The same graph could be represented:

edges = {0: [1]}

The shown code demonstrates that their behavior is the same:

edges0 = {0: [1], 1: [], 2: [], 3: [], 4: []}
print(edges0) # prints {0: [1], 1: [], 2: [], 3: [], 4: []}
print(len(edges0)) # prints 5 (V)
print(edges0[0]) # prints [1]
print(edges0[1]) # prints []
print("\n")
edges1 = {0: [1]}
print(edges1) # prints {0: [1]}
print(len(edges1)) # prints 1 (E)
print(edges1[0] if 0 in edges1 else []) # prints [1]
print(edges1[1] if 1 in edges1 else []) # prints []

The same effect can be achieved in Java by using HashMap.getOrDefault(key, Collections.emptyList()).

My colleague disagrees, but I don't see why this representation would take more than $O(E)$ space.

Answer 1

Just as an initial comment, it's not entirely settled what Bachmann big-oh notation formally means when you have more than one variable. There are multiple competing definitions. But let's leave that aside for now, because I think we all know what you mean by $O(V + E)$ here.

This data structure does indeed use $O(E)$ space in the worst case. The simplest way to see it is by observing that the number of entries in the top-level hash table must be less than or equal to $E$. That is, the number of entries in the top-level hash table is $O(E)$.