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

Time Complexity: Cycle Detection in Directed Graph

O(n + e)

Understanding Time Complexity

We want to understand how long it takes to check if a directed graph has a cycle.

This helps us know how the work grows as the graph gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function hasCycle(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>();
  const recStack = new Set<number>();

  function dfs(node: number): boolean {
    if (recStack.has(node)) return true;
    if (visited.has(node)) return false;

    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph.get(node) || []) {
      if (dfs(neighbor)) return true;
    }

    recStack.delete(node);
    return false;
  }

  for (const node of graph.keys()) {
    if (dfs(node)) return true;
  }
  return false;
}
    

This code checks if a directed graph has a cycle using depth-first search and tracking recursion stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Depth-first search (DFS) visits each node and its neighbors.
• How many times: Each node is visited once, and each edge is checked once during DFS.

How Execution Grows With Input

As the number of nodes and edges grow, the work grows roughly in proportion to their total.

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 linearly with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time to detect a cycle grows linearly with the number of nodes plus edges in the graph.

Common Mistake

[X] Wrong: "The DFS visits nodes multiple times, so time is O(n * e)."

[OK] Correct: Each node is marked visited and processed once, so edges are checked only once, keeping time linear.

Interview Connect

Understanding this time complexity helps you explain how your cycle detection scales with graph size, a key skill in graph problems.

Self-Check

"What if we used an adjacency matrix instead of adjacency lists? How would the time complexity change?"