Bipartite Graph Check in DSA C - Time & Space Complexity

Time Complexity: Bipartite Graph Check

O(n^2)

Understanding Time Complexity

We want to know how the time needed to check if a graph is bipartite changes as the graph grows.

Specifically, how does the number of nodes (n) affect the work done? (Note: In adjacency matrix representation, edges do not impact asymptotic time.)

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Check if graph is bipartite using BFS
bool isBipartite(int graph[][MAX], int n) {
    int color[n];
    for (int i = 0; i < n; i++) color[i] = -1;
    
    for (int start = 0; start < n; start++) {
        if (color[start] == -1) {
            color[start] = 0;
            Queue q;
            q.push(start);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v = 0; v < n; v++) {
                    if (graph[u][v] && color[v] == -1) {
                        color[v] = 1 - color[u];
                        q.push(v);
                    } else if (graph[u][v] && color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}
    

This code checks if a graph is bipartite by coloring nodes using breadth-first search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: BFS dequeues each node once and scans all n possible neighbors (matrix row).
• How many times: n nodes dequeued × n neighbor checks each = O(n²).

How Execution Grows With Input

As the number of nodes (n) grows, the work grows quadratically with n. Edges do not affect asymptotic time (full matrix rows scanned).

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

Pattern observation: The operations grow quadratically with the number of nodes.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly in proportion to n squared due to adjacency matrix neighbor scans.

Common Mistake

[X] Wrong: "The time depends only on the number of nodes like O(n), ignoring neighbor checks."

[OK] Correct: Each node's neighbor check scans the full row of n entries in the matrix.

Interview Connect

Understanding this time complexity helps you explain how graph algorithms scale, a key skill in many coding interviews.

Self-Check

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