On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?

Category: QuestionsOn which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?
Editor">Editor Staff asked 1 month ago

On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?
 
(a) Depends on the number of edges
 
(b) Depends on the number of vertices
 
(c) Is independent of both the number of edges and vertices
 
(d) It depends on both the number of edges and vertices
 
Asked question is from Adjacency Matrix topic in division Graph of Data Structures & Algorithms I
 
The question was asked by my college professor while I was bunking the class.

1 Answers
Editor">Editor Staff answered 1 month ago

Correct option is (c) Is independent of both the number of edges and vertices
 
Explanation: To check if there is an edge between to vertices i and j, it is enough to see if the value of A[i][j] is 1 or 0, here A is the adjacency matrix.