196 views

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 :)

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.

they are saying its B...even I got C.
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.

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. .

1
2,665 views