educative.io

Educative

Time Complexity if we want to ensure that there are no duplicates in the graph

A reader asked the following question:

It seems that the time complexity for “Add Edge” in “Adjacency List” might be O(E) (traverse the list of vertices) to ensure that we are not adding a duplicate.

Hi,

This is Alina from Educative.

In a general graph, there can be parallel edges. Thus, there is no need to check for duplicate edges. If we considered a graph with no parallel edges, a tighter bound on the running time of checking for a duplicate edge would be O(|V|). This is because any vertex, in this case, could have at most |V| - 1 edges to other vertices, whereas |E|, in the worst case is |V| ( |V| - 1 ). Hope this helps!

We hope Educative has inspired you to further your learning! If you have any further concerns/questions/comments, please let us know.

Best Regards,
Alina Fatima | Developer Advocate