Cycle Detection in Directed Graph in DSA C - Time & Space Complexity

Time Complexity: Cycle Detection in Directed Graph

O(n + e)

Understanding Time Complexity

We want to understand how the time needed to find a cycle in a directed graph changes as the graph grows.

Specifically, how does the process of checking each node and its connections scale?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Detect cycle using DFS in directed graph
bool dfs(int node, int visited[], int recStack[], List* graph) {
    visited[node] = 1;
    recStack[node] = 1;
    for (int i = 0; i < graph[node].size; i++) {
        int neighbor = graph[node].edges[i];
        if (!visited[neighbor] && dfs(neighbor, visited, recStack, graph))
            return true;
        else if (recStack[neighbor])
            return true;
    }
    recStack[node] = 0;
    return false;
}

bool isCyclic(int n, List* graph) {
    int visited[n];
    int recStack[n];
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
        recStack[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dfs(i, visited, recStack, graph))
            return true;
    }
    return false;
}
    

This code checks each node using depth-first search to find if a cycle exists in a directed graph.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS visits each node and explores all its edges recursively.
• How many times: Each node is visited once, and each edge is checked once during the DFS calls.

How Execution Grows With Input

As the number of nodes and edges increase, the DFS explores more connections.

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

Pattern observation: The operations grow roughly proportional to the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

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

Common Mistake

[X] Wrong: "The DFS visits each node multiple times, so the time is much higher than linear."

[OK] Correct: Each node is marked visited and explored only once, so repeated visits do not happen, keeping the time linear.

Interview Connect

Understanding this time complexity helps you explain how graph traversal scales and why DFS is efficient for cycle detection.

Self-Check

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