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