Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________?Group of answer choicesO(E)O(E*E)O(V)O(E+V)
Question
Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________?Group of answer choicesO(E)O(E*E)O(V)O(E+V)
Solution
The space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is O(E+V).
Here's why:
-
An adjacency list is a way to represent a graph where an array of lists is used. The size of the array is equal to the number of vertices (V) in the graph.
-
Each list represents the edges (E) of a vertex. In an undirected graph, each edge is connected to two vertices and hence will appear twice in the adjacency list.
-
Therefore, the total space required is proportional to the sum of the number of vertices and twice the number of edges, which simplifies to O(E+V).
Similar Questions
Time Complexity of DFS is? (V – number of vertices, E – number of edges)Group of answer choicesO(V + E)O(E)O(V*E)O(V)
Time complexity to find if there is an edge between 2 particular vertices is _________?Group of answer choicesO(V)O(E)O(1)O(V+E)
What is the worst time complexity of checking node u and v are directly connected by an edge in a graph G = |V, E| when adjacency list is used
For some sparse graph an adjacency list is more space efficient against an adjacency matrix.Group of answer choicesTrueFalse
Adjacency list requires memory of the order of2 pointsθ(V-E)θ(VE)θ(V/E)θ(V+E)
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.