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 time where is vertices and is edges. This is linear in the size of the graph. DFS is fast. For most graphs, is proportional to , so it is effectively where is the number of vertices.
Space complexity is for the data structures used.