Cycle detection in graphs in Data Structures Theory - Time & Space Complexity

Time Complexity: Cycle detection in graphs

O(n + m)

Understanding Time Complexity

When checking if a graph has a cycle, we want to know how the time needed grows as the graph gets bigger.

We ask: How does the work increase when the graph has more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function hasCycle(graph) {
  const visited = new Set();
  const stack = new Set();

  function dfs(node) {
    if (stack.has(node)) return true;
    if (visited.has(node)) return false;

    visited.add(node);
    stack.add(node);

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

    stack.delete(node);
    return false;
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node)) return true;
    }
  }
  return false;
}
    

This code uses depth-first search to check if any path loops back to a node already in the current path, indicating a cycle.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive depth-first search (DFS) visits each node and its neighbors.
• How many times: Each node and edge is checked once during the DFS traversal.

How Execution Grows With Input

As the graph grows, the DFS visits more nodes and edges, so the work grows with both.

Input Size (n nodes, m edges)	Approx. Operations
10 nodes, 15 edges	About 25 checks (nodes + edges)
100 nodes, 200 edges	About 300 checks
1000 nodes, 3000 edges	About 4000 checks

Pattern observation: The work grows roughly in proportion to the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + m)

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

Common Mistake

[X] Wrong: "Cycle detection always takes quadratic time because of nested loops."

[OK] Correct: The DFS visits each node and edge once, so it does not repeatedly check all pairs, keeping the time linear.

Interview Connect

Understanding how cycle detection scales helps you explain your approach clearly and shows you know how to handle bigger graphs efficiently.

Self-Check

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