BFS Breadth First Search on Graph in DSA Typescript - Time & Space Complexity

Time Complexity: BFS Breadth First Search on Graph

O(n + m)

Understanding Time Complexity

We want to understand how the time needed to explore a graph grows as the graph gets bigger using BFS.

How does BFS's work change when the graph has more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function bfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const queue: number[] = [];
  const result: number[] = [];

  queue.push(start);
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}
    

This code explores all nodes reachable from the start node using BFS, visiting neighbors level by level.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs as long as there are nodes in the queue, processing each node once.
• How many times: Each node is visited once, and each edge is checked once when exploring neighbors.

How Execution Grows With Input

As the graph grows, BFS visits every node and checks every edge connected to those nodes.

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

Pattern observation: The work grows roughly in proportion to the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + m)

This means BFS takes time proportional to the total number of nodes plus edges in the graph.

Common Mistake

[X] Wrong: "BFS always takes O(n²) time because it uses nested loops."

[OK] Correct: BFS visits each node and edge only once, so it does not repeatedly check all pairs; it scales with nodes plus edges, not their square.

Interview Connect

Understanding BFS time complexity helps you explain how graph searches work efficiently, a key skill for many coding challenges and real-world problems.

Self-Check

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