CODEWITHSUNDEEP
graph
poddroid
poddroid

Reputation: 855

what is the worst-case running time for finding two given vertices are adjacent in Adjacency matrix implmentation of a graph

What is the worst-case running time for finding two given vertices are adjacent in Adjacency matrix implmentation of a graph? Is that not O(1) as I know the indices of those vertices in the matrix so that I can pick the value in constant time? I read it as O(n^2) in a book. Someone please explain it how to get to this measure.

Thanks

Upvotes: 0

Views: 658

Answers (2)

andrew
andrew

Reputation: 2574

An adjacency matrix occupies O(n^2) memory, which may be where you're confused. But yes lookup given two vertices is O(1), that's the advantage of an adjacency matrix.

Upvotes: 3

oops
oops

Reputation: 11

yes. it is O(1) for the reasons stated by you.

Upvotes: 0

Related Questions