CMI Assignment Question

Question

Let G = (V, E) with |V | = n and |E| = m. What is the worst-case complexity of:

(a) BFS using an adjacency matrix representation of G. O($n^2$ )

(b) BFS using an adjacency list representation of G. O(n + m)

(c) DFS using an adjacency matrix representation of G. O($n^2$ )

(d) DFS using an adjacency list representation of G. O(n + m)

Comments

All the options are correct.