DFS Time Complexity Analysis
What You'll Learn
You'll understand why DFS runtime depends on your graph representation: O(V + E) for adjacency lists and O(V²) for adjacency matrices.
Why Complexity Depends on Representation
DFS visits every vertex once and explores all edges reachable from each vertex. The total work depends on how efficiently you can find those edges.
With Adjacency Lists: O(V + E)
When using adjacency lists, each vertex's neighbors are stored in a direct list. DFS:
- Visits each of the V vertices exactly once
- Iterates through each vertex's neighbor list
- Across all vertices, you examine each edge exactly once (or twice for undirected graphs, still O(E))
Total: O(V) for visiting vertices + O(E) for examining edges = O(V + E)
Think of it like checking off every person in a room (V) and every handshake that happened (E)—you count each thing once.
With Adjacency Matrix: O(V²)
With an adjacency matrix, neighbors aren't pre-listed. For each vertex, DFS must:
- Check every column in that vertex's row to find neighbors
- This means V checks per vertex
- Across V vertices: V × V = V² operations
Even if the graph is sparse (few edges), you still scan entire matrix rows.
Total: O(V²) regardless of edge count
This is like checking every possible pair of people to see if they shook hands, even when most didn't.
Practical Impact
Sparse graphs (few edges) dramatically benefit from adjacency lists. Dense graphs (many edges, where E ≈ V²) make both representations similar in practice.
Key Takeaway: DFS time complexity is O(V + E) with adjacency lists (preferred for sparse graphs) and O(V²) with adjacency matrices, because you must scan entire rows to find neighbors.