Bridges in Graph Tarjan's Algorithm in DSA Typescript - Time & Space Complexity

Time Complexity: Bridges in Graph Tarjan's Algorithm

O(n + m)

Understanding Time Complexity

We want to know how the time needed to find bridges in a graph grows as the graph gets bigger.

Specifically, how the algorithm's steps increase with more nodes and edges.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findBridges(graph: number[][]): [number, number][] {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const bridges: [number, number][] = [];
  let time = 0;

  function dfs(u: number, parent: number) {
    visited[u] = true;
    disc[u] = low[u] = time++;
    for (const v of graph[u]) {
      if (v === parent) continue;
      if (!visited[v]) {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) bridges.push([u, v]);
      } else {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) dfs(i, -1);
  }

  return bridges;
}
    

This code finds all bridges (edges that if removed increase graph parts) using DFS and tracking discovery times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Depth-first search (DFS) visits each node and its edges once.
• How many times: Each node is visited once, and each edge is checked once.

How Execution Grows With Input

As the number of nodes and edges grow, the algorithm checks each node and edge once.

Input Size (n nodes, m edges)	Approx. Operations
10 nodes, 15 edges	About 25 operations (visiting nodes + edges)
100 nodes, 200 edges	About 300 operations
1000 nodes, 3000 edges	About 4000 operations

Pattern observation: Operations grow roughly in proportion to nodes plus edges.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the number of nodes and edges in the graph.

Common Mistake

[X] Wrong: "The algorithm checks every possible path, so it must be exponential."

[OK] Correct: The DFS visits each node and edge only once, not all paths, so it runs efficiently in linear time.

Interview Connect

Understanding this linear time complexity helps you explain how graph algorithms handle large data efficiently.

Self-Check

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