ericdrowell/BigOCheatSheet — pull request #12 by qpleple (2013-05-04 16:17:45+00:00)
Title: Remove a vertex in an adjacency list takes O(V+E)

When removing a vertex u in a graph represented as an Adjacency List, you have to go through all the other vertices and check if they have an edge to u. This takes time O(|V| + |E|).

In the situation where |E| > |V|, then it can be simply in O(|E|). But it's not always true (for eg, |E| = 2 and |V| = 1,000,000).