Menu
I read here that for Undirected graph the space complexity is O(V + E) when represented as a adjacency list where V and E are number of vertex and edges respectively.
My analysis is, for a completely connected graph each entry of the list will contain |V|-1 nodes then we have a total of |V| vertices hence, the space complexity seems to be O(|V|*|V-1|) which seems O(|V|^2) what I am missing here?
378
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.
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. So, say you have a sparse graph, where degree of each vertex is 2.
In this representation, for every vertex we store its neighbours. In the worst case, if a graph is connected O(V) is required for a vertex and O(E) is required for storing neighbours corresponding to every vertex . Thus, overall space complexity is O(|V|+|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).
You analysis is correct for a completely connected graph. However, note that for a completely connected graph the number of edges E is O(V^2) itself, so the notation O(V+E) for the space complexity is still correct too.
However, the real advantage of adjacency lists is that they allow to save space for the graphs that are not really densely connected. If the number of edges is much smaller than V^2, then adjacency lists will take O(V+E), and not O(V^2) space.
Note that when you talk about O-notation, you usually have three types of variables (or, well, input data in general). First is the variables dependence on which you are studying; second are those variables that are considered constant; and third are kind of "free" variables, which you usually assume to take the worst-case values. For example, if you talk about sorting an array of N integers, you usually want to study the dependence of sorting time on N, so N is of the first kind. You usually consider the size of integers to be constant (that is, you assume that comparison is done in O(1), etc.), and you usually consider the particular array elements to be "free", that is, you study that runtime for the worst possible combination of particular array elements. However, you might want to study the same algorithm from a different point of view, and it will lead to a different expression of complexity.
For graph algorithms, you can, of course, consider the number of vertices V to be of first kind, and the number of edges to be the third kind, and study the space complexity for given V and for the worst-case number of edges. Then you indeed get O(V^2). But it is also often useful to treat both V and E as variables of the first type, thus getting the complexity expression as O(V+E).
101
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
