0
$\begingroup$

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.

$\endgroup$
  • 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 '18 at 16:40
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.