DFS Depth First Search on Graph in DSA C - Time & Space Complexity

Time Complexity: DFS Depth First Search on Graph

O(n^2)

Understanding Time Complexity

We want to understand how the time taken by Depth First Search (DFS) changes as the graph size grows.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code visits all nodes reachable from the starting node using DFS on an adjacency matrix graph.

Identify Repeating Operations

• Primary operation: The for-loop inside dfs that checks all possible neighbors of the current node.
• How many times: This loop runs for each node visited, and dfs is called recursively for each unvisited neighbor.

How Execution Grows With Input

As the number of nodes (n) increases, DFS visits each node once and performs n neighbor checks for each visited node (adjacency matrix).

Input Size (n)	Approx. Operations
10 nodes	About 100 operations (10 × 10 checks)
100 nodes	About 10,000 operations (100 × 100)
1000 nodes	About 1,000,000 operations (1000 × 1000)

Pattern observation: Operations grow quadratically with the number of nodes, so more nodes mean much more work.

Final Time Complexity

Time Complexity: O(n^2)

This means DFS takes time proportional to the square of the number of nodes in the graph.

Common Mistake

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

[OK] Correct: The nested loop is inside recursion, but for adjacency matrix, the loop scans all n columns for each of the n nodes, so total work is O(n^2), not dependent on e.

Interview Connect

Understanding DFS time complexity helps you explain how graph traversal scales, a key skill in many coding problems and interviews.

Self-Check

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