Topological Sort Using DFS in DSA C - Time & Space Complexity

Time Complexity: Topological Sort Using DFS

O(V^2)

Understanding Time Complexity

We want to understand how the time needed to perform topological sort using DFS changes as the graph size grows.

The question is: how does the number of steps grow when we have more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void dfs(int node, int visited[], int stack[], int *top, int graph[][N], int n) {
    visited[node] = 1;
    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i, visited, stack, top, graph, n);
        }
    }
    stack[(*top)++] = node;
}

void topologicalSort(int graph[][N], int n) {
    int visited[N] = {0};
    int stack[N];
    int top = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, stack, &top, graph, n);
        }
    }
}
    

This code performs a topological sort on a graph using Depth-First Search (DFS).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS visits each node once and scans the entire row of the adjacency matrix (checks all possible outgoing edges).
• How many times: Each node is visited once; from each node, the loop runs n times (once for each possible neighbor), totaling O(n^2).

How Execution Grows With Input

As the number of nodes grows, the work grows quadratically with nodes (independent of actual edges due to matrix representation).

Input Size	Approx. Operations
10 nodes	About 100 checks (10 nodes * 10 checks/node)
100 nodes	About 10,000 checks (100 * 100)
1000 nodes	About 1,000,000 checks (1000 * 1000)

Pattern observation: The operations grow quadratically with the number of nodes.

Final Time Complexity

Time Complexity: O(V^2)

This means the time grows quadratically with the number of nodes (V) in the graph. (For adjacency lists, it would be O(V + E).)

Common Mistake

[X] Wrong: "DFS takes O(V + E) time because each edge is checked once."

[OK] Correct: Although there appears to be a nested loop, no—in adjacency matrix, every node scans all V possible neighbors (including non-edges), so total work is O(V^2), not O(V + E).

Interview Connect

Understanding this time complexity helps you explain how graph algorithms scale, a key skill in many coding challenges and real projects.

Self-Check

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