Topological Sort Using Kahn's Algorithm BFS in DSA C - Time & Space Complexity

Time Complexity: Topological Sort Using Kahn's Algorithm BFS

O(V + E)

Understanding Time Complexity

We want to understand how the time needed to perform topological sort using Kahn's Algorithm grows as the graph size increases.

Specifically, how the number of nodes and edges affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void kahnTopologicalSort(int V, vector<int> adj[]) {
    vector<int> indegree(V, 0);
    for (int i = 0; i < V; i++) {
        for (int node : adj[i]) {
            indegree[node]++;
        }
    }
    queue<int> q;
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        // process u
        for (int node : adj[u]) {
            indegree[node]--;
            if (indegree[node] == 0) q.push(node);
        }
    }
}
    

This code performs a topological sort on a graph with V nodes using Kahn's BFS algorithm.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing all edges and nodes in the graph.
• How many times: Each edge is visited once when counting indegrees and once when processing nodes from the queue.

How Execution Grows With Input

The work grows roughly with the number of nodes plus the number of edges.

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

Pattern observation: The operations increase linearly with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(V + E)

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

Common Mistake

[X] Wrong: "The algorithm runs in O(V²) because of nested loops."

[OK] Correct: The inner loops do not run for all pairs; they run once per edge, so total work depends on edges, not all pairs of nodes.

Interview Connect

Understanding this time complexity helps you explain how graph algorithms scale and why Kahn's method is efficient for topological sorting.

Self-Check

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