Introduction

Depth-first search, or DFS, is one of the standard graph traversal algorithms. The textbook answer for its complexity is usually O(V + E) time and O(V) space, but those numbers depend on how the graph is stored and whether the implementation is recursive or iterative. Once you break the algorithm into visited vertices, scanned edges, and stack usage, the result becomes straightforward.

Why DFS Runs in O(V + E) Time

Assume the graph uses an adjacency list. DFS visits each reachable vertex once and scans each adjacency list once. Across the full traversal, that means it touches every vertex and every edge a bounded number of times.

Here is a simple iterative implementation in Python:

1def dfs(graph, start):
2    visited = set()
3    stack = [start]
4    order = []
5
6    while stack:
7        node = stack.pop()
8        if node in visited:
9            continue
10
11        visited.add(node)
12        order.append(node)
13
14        for neighbor in reversed(graph[node]):
15            if neighbor not in visited:
16                stack.append(neighbor)
17
18    return order
19
20
21graph = {
22    "A": ["B", "C"],
23    "B": ["D"],
24    "C": ["E"],
25    "D": [],
26    "E": []
27}
28
29print(dfs(graph, "A"))

The loop does not multiply into O(V * E). Each vertex is marked once, and each edge in the adjacency lists is considered while iterating over neighbors. That gives:

• 'O(V) for vertex visits'
• 'O(E) for neighbor scans'
• total O(V + E)

In an undirected graph, each edge appears in two adjacency lists, but that is still linear in the size of the input representation.

Why the Space Complexity Is O(V)

DFS needs memory for two main structures:

• a visited set
• a traversal stack, either explicit or from recursion

Both can grow to the number of vertices in the worst case. A path-shaped graph is the easiest way to see this. If the graph is just a long chain, DFS may hold nearly every vertex on the current path before it finishes.

A recursive version has the same asymptotic behavior:

1def dfs_recursive(graph, node, visited=None):
2    if visited is None:
3        visited = set()
4
5    visited.add(node)
6    print(node)
7
8    for neighbor in graph[node]:
9        if neighbor not in visited:
10            dfs_recursive(graph, neighbor, visited)
11
12
13dfs_recursive(graph, "A")

The difference is practical rather than asymptotic. Recursive DFS uses the language call stack. Iterative DFS uses an explicit stack you control.

Representation Changes the Result

The standard O(V + E) analysis assumes adjacency lists. If the graph is stored as an adjacency matrix, finding neighbors requires scanning an entire row of length V for each vertex. That changes the time complexity to O(V^2).

So the correct statement is:

• adjacency list DFS: O(V + E) time
• adjacency matrix DFS: O(V^2) time

This is why sparse graphs are usually represented with adjacency lists.

Trees Are a Special Case

For a tree with N nodes, the edge count is N - 1, so DFS is often described as O(N) time. Space is often described as O(H), where H is the tree height, because the traversal stack only holds the current path.

That still fits the graph result. A tree is just a constrained graph with fewer edges.

Common Pitfalls

• Forgetting that O(V + E) assumes adjacency lists.
• Ignoring the visited set in cyclic graphs.
• Treating recursion as free. Deep graphs can overflow the call stack even when the big-O analysis looks fine.
• Confusing tree complexity with general graph complexity.
• Claiming DFS is O(E) and skipping the cost of vertex bookkeeping.

Summary

• DFS on an adjacency-list graph runs in O(V + E) time.
• Its auxiliary space is O(V) because of the stack and visited set.
• Recursive and iterative DFS have the same asymptotic complexity.
• With an adjacency matrix, DFS becomes O(V^2) time.
• Trees are often summarized as O(N) time because they have N - 1 edges.