shouldn’t the complexity be O(VE) as the vertex has to be removed from array and then the edge to vertex must be removed from all other vertices.
Hi Mahendra ,
This is Maida from Educative.
So, there has to be this code:
for v in g.vertices():
for e in v.adjacency():
The outer loop is O(V) and the inner one is O(E). So, overall it should be O(VE). That is mathematically not wrong, but not a tight bound. It would be a tight bound if every vertex had O(E)adjacent vertices. That is a loose bound.
If we think closely, we are going left to right in the adjacencies of each vertex and top to bottom over vertices one by one. If the graph had no edges, only vertices, it would still go over all the vertices, which is O(V).
Now, add one edge to the graph. Assuming it is an undirected graph, now, we are doing V + 2 operations (or V + 1) for a directed graph. Because we loop over all V vertices, plus in one adjacency list, we pick one edge. Add a second edge and you are doing V + 2 operations and so on. So, it is O(V + E) as a tight bound. This is a tight bound on the worst case.
The number of edges in the worst case is O(V^2) when every vertex is connected to every other vertex. But E is the number of edges, no matter what. Whether there are 0 edges, 1 edge, or V^2.
Let understand this with the help of an example. Take this graph:
V = 6 and E = 8. And we go over the adjacency list, touching 6 vertices and 8 items in the linked lists, so 6 + 8, which is O(V + E). Increase the number of edges as much as you want and this is still valid.
We hope Educative has inspired to further your learning, and please drop us a note if you have any other questions or concerns.
Best Regards,
Maida | Developer Advocate
educative.io
1 Like