Adjacency Matrix Representation in DSA C - Time & Space Complexity

Time Complexity: Adjacency Matrix Representation

O(n²)

Understanding Time Complexity

We want to understand how the time to work with an adjacency matrix changes as the graph grows.

How does the number of nodes affect the steps needed to check or build connections?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Print all edges in an adjacency matrix
void printEdges(int n, int matrix[n][n]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                printf("Edge from %d to %d\n", i, j);
            }
        }
    }
}
    

This code checks every possible connection between nodes in a graph represented by an adjacency matrix.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over all nodes to check edges.
• How many times: Outer loop runs n times, inner loop runs n times for each outer loop, total n x n = n² times.

How Execution Grows With Input

As the number of nodes increases, the steps to check all edges grow quickly because every node is checked against every other node.

Input Size (n)	Approx. Operations
10	100
100	10,000
1000	1,000,000

Pattern observation: The operations grow by the square of the number of nodes, so doubling nodes makes operations about four times more.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows quickly as the graph gets bigger, because every node is checked against every other node.

Common Mistake

[X] Wrong: "Checking edges in an adjacency matrix takes only O(n) time because we just loop once."

[OK] Correct: The matrix has n rows and n columns, so you must check n x n positions, not just n.

Interview Connect

Understanding adjacency matrix time complexity helps you explain graph operations clearly and choose the right graph representation in real problems.

Self-Check

"What if we used an adjacency list instead of a matrix? How would the time complexity for checking edges change?"