Question

Time Complexity of DFS is? (V – number of vertices, E – number of edges)

(a) O(V + E)

(b) O(V)

(c) O(E)

(d) O(V*E)

The question was asked in an interview for job.

This question is from Depth First Search topic in chapter Graph Search of Data Structures & Algorithms II

Answer 1

The correct choice is (a) O(V + E)

To explain: The Depth First Search explores every node once and every edge once (in worst case), so it’s time complexity is O(V + E).