I'm trying to reason about the time complexity of removing a vertex from a graph represented as an adjacency list, which has $n$ vertices and $e$ edges. It is a directed graph, and the list associated to any particular vertex $v_i$ contains the vertices directly reachable from $v_i$ (i.e. the edges with origin $v_i$).
Let's assume that the graph is represented as a hash map, which pairs a certain vertex with its adjacency list, which is a linked list. Iterating over a linked list of $m$ elements has a time complexity of $O(m)$, and deleting a node of the list as one iterates over it has constant complexity $O(1)$.
In order to remove a vertex $v_d$ I would need to:
- Remove the pair with key $v_d$ from the hash map (which is $O(1)$).
- Iterate over the adjacency lists of the rest of the vertices, removing any occurrence of $v_d$.
The second step would mean iterating over each vertex $v_i$ in the key set of the hash map (~$n$ vertices, after having removed one), and for each vertex $v_i$ iterate over its adjacency list, which is of length $e_i$.
Now, it is clear that $\displaystyle\sum_{i=1}^{n} e_i = e$, so my first thought is that the time complexity of the second step is $O(e)$, and so is the total cost of removing a vertex in this situation. Note how this is independent of the number of vertices in the graph.
However, I'm thinking about the case in which there are no edges at all. In that case, step two still requires iterating over the whole list of vertices, so I'm lead to believe that the number of vertices has to play some role inthe time complexity of the method.
What is the actual time complexity in this set up and how can you reconcile the two (apparently contradictory) conclusions I've reached?
