In the Introduction to Algorithms Book By Thomas H. Cormen, Third Edition, they give an approximation algorithm for the Vertex Cover Problem with 2-approximation ratio:
Where G is undirected graph. The complexity of this algorithm is O(V+E). I do not know why. It should be O(E) since the while loop in line 3 clearly will loop |E| times (E is the set of edges in G). The cost of line 6 is at most 1?