Question

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.

Answer 1

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.