Time Complexity for Creating a Graph from a File

Problem Detail: 

Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example:

0 5 0 7 2 3 4 5 1 5 . . . 

I want to create a graph (adjacency list) by reading this file line-by-line. For each line, I will create an edge between the two vertices. Of course, if the vertex doesn't exist yet, then I will add it before creating the edge.

I read here of an algorithm that builds a graph with a time complexity of $O(|V| + |E|)$ where $V$ = set of vertices and $E$ = set of edges. That makes sense to me. However my algorithm doesn't insert the vertices in a loop first and then insert all of the edges in another loop second. My algorithm just adds the vertices as it's looping through the edges.

My question is if my algorithm is $O(|E|)$? It seems like that can't be right, but I read here that when calculating the time complexity you don't take into account if statements. That's exactly what my vertex creation would be -- an if statement that checks if the node exists in the middle of my looping through all the edges.

Asked By : battmanz

Answered By : Karolis Juodelė

You forget that $O(|E|) \subset O(|E|+|V|)$ and $O(|E|+|V|) \subset O(|E|)$. Though It's actually $O(|E|\ln|V|)$, because checking if a vertex has been inserted is hardly $O(1)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14223