Menu
I am reading "Algorithms Design" By Eva Tardos and in chapter 3 it is mentioned that adjacency matrix has the complexity of O(n^2) while adjacency list has O(m+n) where m is the total number of edges and n is the total number of nodes. It says that in-case of adjacency list we will need only lists of size m for each node.
Won't we end up with something similar to matrix in case of adjacency list as we have lists,which are also 1D arrays. So basically it is O(m*n) according to me. Please guide me.
657
A vertex can have at most O(|V|) neighbours and in worst can we would have to check for every adjacent vertex. Therefore, time complexity is O(|V|) .
Matrices have better cache performance than adjacency lists though, because of sequential access, so for a somewhat dense graphs, scanning a matrices can make more sense.
Originally Answered: why is the space complexity of adjacency list O(v+e) and not O(v*e)? A2A. It is because the adjacency list only contains the neighbours of each vertex.
An adjacency list is a list of lists. Each list corresponds to a vertex u and contains a list of edges (u, v) that originate from u. Thus, an adjacency list takes up Θ(V + E) space. An adjacency matrix is a |V |×|V | matrix of bits where element (i, j) is 1 if and only if the edge (vi,vj) is in E.
An adjacency matrix keeps a value (1/0) for every pair of nodes, whether the edge exists or not, so it requires n*n space.
An adjacency list only contains existing edges, so its length is at most the number of edges (or the number of nodes in case there are fewer edges than nodes).
It says that in-case of adjacency list we will need only lists of size m for each node.
I think you misunderstood that part. An adjacency list does not hold a list of size m for every node, since m is the number of edges overall.
In a fully connected graph, there is an edge between every pair of nodes so both adjacency list and matrix will require n*n of space, but for every other case - an adjacency list will be smaller.
71
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
