Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________

Category: QuestionsSpace complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________
Editor">Editor Staff asked 4 weeks ago

Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________
 
(a) O(E)
 
(b) O(V*V)
 
(c) O(E+V)
 
(d) O(V)
 
The question is from Adjacency List in section Graph of Data Structures & Algorithms I
 
This question was posed to me in an interview for job.

1 Answers
Editor">Editor Staff answered 4 weeks ago

The correct option is (c) O(E+V)
 
Easiest explanation – In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.