Nitin Agarwal
Reputation: 43
For undirected graph, why memory requirement for adjacency list representation is θ(V+E) and not θ(V+2E) ?
In case of undirected graph, since there are 2E edges in the adjacency list representation then why the memory requirement is same as that for directed graph?
Upvotes: 1
Views: 202
Answers (1)
gue
Reputation: 2028
Theta(V+E) = Theta(V+2E) since 2 is a constant and makes no difference in big-O notation.
Upvotes: 1
Related Questions
- Why adjacency list uses array of vectors and not vector of vectors in graphs in c++?
- Why space complexity of adjacency list representation is O(V+E) not O(E)?
- C++ Adjacency List Representation of Graphs
- Why Graph adjacency is not defined as adjacency set, but rather adjacency list?
- size edges and vertex of adjancency list c++
- Why are operations in an adjacency list O(|E|/|V|)$?
- Storage of different-sized edges in directed adjacency-list graph
- How is the memory required for adjacency list representation is O(V+E)?
- Adjacency Lists for graph representation using space O(number of edges)
- graphs representation : adjacency list vs matrix