Multiple choice

Consider an undirected graph G with 'n' vertices and 'e' edges. What is the time taken by Depth First Search (DFS), if the graph is represented by: (i) adjacency matrix, and (ii) adjacency list?

  1. O(n2), O(n)

  2. O(n2), O(e)

  3. O(e), O(n2)

  4. O(e + n), O(e)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

For an adjacency matrix, DFS takes O(n^2) because you must check all possible edges for each vertex. For an adjacency list, it takes O(n + e), which is often simplified to O(e) if the graph is connected or e >= n.

Keep practicing — related questions