DFS Time Complexity | DFS Meaning

The Depth-First Search or DFS is a traversing type technique just like the Breadth-First Search or BFS that also can be used to color or visit graphs based on a real-life problem. DFS time complexity may differ by implementation procedure. In this post, the time complexity of DFS will be discussed.

Time Complexity of DFS

Considering the below graphs to find out the time complexity of the DFS algorithm. There are V-th (V1, V2, V3, V4, V5, V6) vertices and E-th (E1, E2, E3, E4, E5, E6) edges in figure 1. So the summation will be,

Fig. 01: Example of a graph for DFS

V-th = V1+V2+V3+V4+V5+V6

E-th = E1+E2+E3+E4+E5+E6

As usual, we will use the Big O notation. So, the question is, why should we use the Big O notation? Because Big O notation is used to represent the run time or space requirements based on the problem input size. As the input size matter in the DFS just like the BFS technique and we have to find the run time complexity for this problem.

First of all, DFS can be implemented using the Recursive function and Stack procedure.

Time Complexity of DFS using Recursive Function

We have to visit all the vertices and edges to complete the DFS technique of a graph. Then the time needed to visit all vextices and edges one's need,

Time Complexity = O ((V1+V2+V3+V4+V5+V6)+(E1+E2+E3+E4+E5+E6))

= O (V-th + E-th)

= O (th will be considere as Total of V & E)

= O (V + E)

Time Complexity of DFS using Recursive Function O (V + E). This recursive procedure increased the running time for the DFS. So, the stack will overflow. We might need to be transferred in another procedure.