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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ There's no reason an operation can't be both $O(|V|)$ and $O(|E|)$, but that probably is not what you mean. $|E|$ is not the number of edges for a single vertex. Try to take a good look what the maximum number of edges connected to a single vertex can be. $\endgroup$– Discrete lizard ♦Mar 5, 2018 at 16:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
In an adjacency list each vertex $u \in V$ is associated with a list of adjacent vertices.
Given a graph $G=(V,E)$, in order to check if the edge $(u,v) \in E$ you need to check whether $v \in \text{adjacent[u]}$.
A node can have at most $O(|V|)$ neighbors, from here the complexity follows.
$\begingroup$
$\endgroup$
Every vertex at most can have an edge with every other vertex which is $O(|V|)$ elements in the adjacency list per vertex. $|V|$ is just a tighter bound which has to be true due the first claim.
