Course contentsShow
← Computer Science
Lesson 717 of 2,87217. Graph Traversal AlgorithmsFree lesson

DFS Time Complexity Analysis

Analyze DFS runtime as O(V + E) for adjacency lists and O(V²) for adjacency matrices.

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.