Question

I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why time complexity in an adjacency list to check would be $O(|V|)$, where $V$ represents the vertices. Shouldn't it be $O(|E|)$ instead? Because in the worst case, it needs to traverse through all of the elements (edges) in a linked list of a certain vertex.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top