Time complexity to check if an edge exists between two vertices would be ___________

Category: QuestionsTime complexity to check if an edge exists between two vertices would be ___________
Editor">Editor Staff asked 1 month ago

Time complexity to check if an edge exists between two vertices would be ___________
 
(a) O(V*V)
 
(b) O(V+E)
 
(c) O(1)
 
(d) O(E)
 
My doubt is from Incidence Matrix and Graph Structured Stack topic in portion Graph of Data Structures & Algorithms I
 
This question was posed to me during an online interview.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct answer is (d) O(E)
 
Best explanation: We have to check for all edges, in the worst case the vertices will have no common edge.