Question

What is the worst-case time complexity of depth first search of a graph with ‘V’ nodes and ‘E’ edges?

• A. \(O(V + E)\)
• B. \(O(V)\)
• C. \(O(E)\)
• D. \(O(V \times E)\)

Hint:

DFS uses \(O(V + E)\) because it traverses all nodes and adjacent edges.

Answer 1

The Correct Option is A

In DFS, each vertex and each edge is visited once in the worst case. Hence, the time complexity is \(O(V + E)\).