DFS Depth First Search on Graph in DSA Typescript - Time & Space Complexity

Time Complexity: DFS Depth First Search on Graph

O(n + e)

Understanding Time Complexity

We want to understand how the time taken by Depth First Search (DFS) changes as the graph size grows.

How does DFS scale when exploring nodes and edges in a graph?

Scenario Under Consideration

Analyze the time complexity of the following DFS code on a graph.

function dfs(node: number, graph: number[][], visited: boolean[]): void {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor, graph, visited);
    }
  }
}
    

This code visits each node and explores all its neighbors recursively.

Identify Repeating Operations

Look for loops and recursive calls that repeat work.

• Primary operation: Visiting each node and checking its neighbors.
• How many times: Each node is visited once, and each edge is checked once.

How Execution Grows With Input

As the graph grows, DFS visits all nodes and edges once.

Input Size (n nodes, e edges)	Approx. Operations
10 nodes, 15 edges	About 10 visits + 15 edge checks = 25 operations
100 nodes, 200 edges	About 100 visits + 200 edge checks = 300 operations
1000 nodes, 5000 edges	About 1000 visits + 5000 edge checks = 6000 operations

Pattern observation: Operations grow roughly proportional to nodes plus edges.

Final Time Complexity

Time Complexity: O(n + e)

This means DFS takes time proportional to the total number of nodes and edges in the graph.

Common Mistake

[X] Wrong: "DFS always takes O(n²) time because it uses recursion and loops."

[OK] Correct: DFS visits each node and edge only once, so it does not repeat work unnecessarily. The time depends on nodes plus edges, not their square.

Interview Connect

Understanding DFS time complexity helps you explain how graph traversal scales and why it is efficient for many problems.

Self-Check

"What if the graph is represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"