Time Complexity of DFS

DFS visits every vertex exactly once (thanks to the visited array). For each vertex, it loops through all its neighbors. Across all vertices, the total number of neighbor iterations equals the number of edges times two (for undirected graphs) or the number of edges (for directed graphs).

So DFS runs in $O(V + E)$ time where $V$ is vertices and $E$ is edges. This is linear in the size of the graph. DFS is fast. For most graphs, $E$ is proportional to $V$, so it is effectively $O(n)$ where $n$ is the number of vertices.

Space complexity is $O(V)$ for the data structures used.