Articulation Points in Graph in DSA C - Time & Space Complexity

Time Complexity: Articulation Points in Graph

O(V + E)

Understanding Time Complexity

We want to know how the time needed to find articulation points changes as the graph grows.

How does the algorithm's work increase when the graph has more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void APUtil(int u, int visited[], int disc[], int low[], int parent[], int ap[], int V, list adj[]) {
    static int time = 0;
    int children = 0;
    visited[u] = 1;
    disc[u] = low[u] = ++time;

    for (auto v : adj[u]) {
        if (!visited[v]) {
            children++;
            parent[v] = u;
            APUtil(v, visited, disc, low, parent, ap, V, adj);
            low[u] = min(low[u], low[v]);
            if (parent[u] == -1 && children > 1)
                ap[u] = 1;
            if (parent[u] != -1 && low[v] >= disc[u])
                ap[u] = 1;
        } else if (v != parent[u]) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

This code finds articulation points using DFS traversal and tracks discovery and low times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Depth-first search (DFS) visits each vertex and edge once.
• How many times: Each vertex is visited once; each edge is checked once or twice.

How Execution Grows With Input

As the graph grows, the algorithm visits every node and edge once, so work grows with nodes plus edges.

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

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

Final Time Complexity

Time Complexity: O(V + E)

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

Common Mistake

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

[OK] Correct: The algorithm uses DFS to visit each node and edge only once, not all pairs, so it is faster than O(V²).

Interview Connect

Understanding this linear time complexity helps you explain how graph traversal algorithms efficiently find critical points.

Self-Check

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