Time Complexity of DFS is? (V – number of vertices, E – number of edges)Group of answer choicesO(V + E)O(E)O(V*E)O(V)

Step 1: Break Down the Problem

To determine the time complexity of Depth-First Search (DFS), we need to consider the operations that DFS performs on a graph represented with vertices and edges.

Step 2: Relevant Concepts

• In DFS, each vertex is visited exactly once.
• Each edge is examined once when traversed.

Step 3: Analysis and Detail

1. Vertex exploration:

   • When DFS visits a vertex, it does some operations which takes constant time $O(1)$.
   • For $V$ vertices, the total time complexity for visiting all vertices is $O(V)$.

2. Edge exploration:

   • For each vertex, DFS explores all its adjacent edges.
   • In a graph, the total number of edges is $E$.
   • Therefore, DFS will check the adjacent edges of all vertices, resulting in a time complexity of $O(E)$.

Step 4: Verify and Summarize

Combining both components, the total time complexity of DFS is: $O(V) + O(E) = O(V + E)$

Final Answer

Thus, the time complexity of DFS is O(V + E).