Bipartite Graph Check in DSA Typescript - Time & Space Complexity

Time Complexity: Bipartite Graph Check

O(n + e)

Understanding Time Complexity

We want to know how long it takes to check if a graph can be split into two groups without edges inside the same group.

How does the time needed grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isBipartite(graph: number[][]): boolean {
  const n = graph.length;
  const colors = new Array(n).fill(-1);

  function dfs(node: number, color: number): boolean {
    if (colors[node] !== -1) return colors[node] === color;
    colors[node] = color;
    for (const neighbor of graph[node]) {
      if (!dfs(neighbor, 1 - color)) return false;
    }
    return true;
  }

  for (let i = 0; i < n; i++) {
    if (colors[i] === -1 && !dfs(i, 0)) return false;
  }
  return true;
}
    

This code checks if the graph is bipartite by coloring nodes using depth-first search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the graph grows, the time to check grows with the number of nodes and edges.

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

Pattern observation: The work grows roughly with the total nodes plus edges, so bigger graphs take proportionally more time.

Final Time Complexity

Time Complexity: O(n + e)

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

Common Mistake

[X] Wrong: "The DFS runs in O(n²) because it looks at all pairs of nodes."

[OK] Correct: The DFS only visits neighbors of each node, so it depends on actual edges, not all pairs.

Interview Connect

Understanding this time complexity helps you explain how graph traversal scales and shows you can analyze recursive algorithms clearly.

Self-Check

"What if we used a queue and breadth-first search (BFS) instead of DFS? How would the time complexity change?"