3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It depends on the data structure you use. For instance if you store the adjacency list as a map of lists the time complexity is O(E) for exactly the reasons you mention. It is the best time complexity you can get for this. But if you use a list of lists you might end up implementing a O(EV) time complexity (e.g.: going through V vertices to check if the tail vertex exists for each edge). $\endgroup$ – marcv81 Jun 13 '16 at 12:53
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ If I were to use a Java ArrayList to store my vertices, and I used the vertex label from the file to index into the backing array, then wouldn't checking if the vertex existed be O(1)? $\endgroup$ – battmanz Sep 9 '13 at 5:18
  • $\begingroup$ Sure, if the labels are $0, 1, 2, \dots n$. The insertion/allocation costs can also be hidden that way. Though, should you ever end up actually implementing the algorithm, I'd advise against such trickery. It's best not to demand too much from your inputs :). $\endgroup$ – Karolis Juodelė Sep 9 '13 at 5:48
  • $\begingroup$ If $|V|$ is large enough random array lookups are not constant time on real machines, because of address translation. See this paper. $\endgroup$ – adrianN Sep 9 '13 at 8:20
  • 1
    $\begingroup$ It depends on the model whether or not you have to add the $\log$-part, e.g., we say bucket sort is linear time. $\endgroup$ – Pål GD Sep 9 '13 at 8:51
  • $\begingroup$ So if I demand a lot from my inputs :), then my algorithm would run in O(|E|) time? Is that correct? $\endgroup$ – battmanz Sep 9 '13 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.