in Algorithms retagged by
196 views
0 votes
0 votes

in Algorithms retagged by
by
196 views

3 Answers

1 vote
1 vote
Best answer

answer C) option 
suppose we have vertex of graph with 4 vertices so  we need 4 *4 ,matrix which will show that either edges is present in the graph or not if edge is present than mark it as 1 if no edge is present than put zero in that particular slot we need O(V2) 

still we need correction in option :)

selected by
1 vote
1 vote
Answer will be C : 0(N ^ 2 ).

because we are representing the graph in matrix which have number of rows  equals to number of columns = N ( Total nodes )

And also,  adjacency matrix were independent of edges,  it will always take O(N^2) space to represent graph as adjacency matrix,

either graph have no edges , few edges or any number of edges.

2 Comments

they are saying its B...even I got C.
0
0
No that's not possible,  O(V + E ) is only possible when we stored the graph with adjacency list

and graph have linear number of edges ( No dense graph )

In case of adjacency matrix it will be always O(N^2) .

You can check it on google.
0
0
0 votes
0 votes

Answer is c : O (v2) because 

In graph, adjacency matrix were independent of edges. It will always takes O(v2) space required to store adjacency matrix. .