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

Time Complexity: Bridges in Graph Tarjan's Algorithm

O(n + m)

Understanding Time Complexity

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

Specifically, how does the algorithm's work change when the number of nodes and edges increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void dfs(int u, int parent) {
    visited[u] = true;
    disc[u] = low[u] = ++time;
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) {
                // (u, v) is a bridge
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
}
    

This code runs a depth-first search to find bridges by tracking discovery and low times for each node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The DFS visits each node once and checks all its edges.
• How many times: Each edge is checked at most twice (once from each end).

How Execution Grows With Input

As the number of nodes (n) and edges (m) grow, the algorithm visits each node once and explores all edges connected to it.

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

Pattern observation: The work grows roughly in a straight line with the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + m)

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

Common Mistake

[X] Wrong: "The algorithm checks every possible pair of nodes, so it must be O(n²)."

[OK] Correct: The algorithm only visits each edge once or twice, not all pairs of nodes, so it does not do n squared work.

Interview Connect

Understanding this linear time complexity helps you explain why Tarjan's algorithm is efficient for large graphs and shows your grasp of graph traversal techniques.

Self-Check

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