Question

The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________

(a) O(V)

(b) O(E^2)

(c) O(E)

(d) O(V^2)

This intriguing question originated from Adjacency Matrix in division Graph of Data Structures & Algorithms I

This question was posed to me by my college professor while I was bunking the class.

Answer 1

The correct option is (d) O(V^2)

Explanation: As V entries are 0, a total of V^2-V entries are to be examined.