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?"

Practice

1. What does an adjacency matrix represent in graph theory?

easy

A. A 2D array showing connections between nodes

B. A list of nodes in the graph

C. A sequence of edges in order

D. A tree structure of nodes

Solution

1. Step 1: Understand adjacency matrix concept

   An adjacency matrix is a 2D array where rows and columns represent nodes.

2. Step 2: Identify what the matrix stores

   Each cell shows if an edge exists between two nodes (1 for connected, 0 for not).

3. Final Answer:

   A 2D array showing connections between nodes -> Option A

4. Quick Check:

   Adjacency matrix = 2D array [OK]

Hint: Adjacency matrix is always a 2D grid of node connections [OK]

Common Mistakes:

• Confusing adjacency matrix with adjacency list
• Thinking it stores node values instead of edges
• Assuming it is a sequence or tree

2. Which of the following is the correct way to declare a 4x4 adjacency matrix in C?

easy

A. int matrix[4];

B. int matrix[4][4];

C. int matrix[];

D. int matrix[4,4];

Solution

1. Step 1: Recall C array declaration syntax

   In C, a 2D array is declared as type name[rows][columns].

2. Step 2: Match syntax for 4x4 matrix

   For 4 rows and 4 columns, it is int matrix[4][4];

3. Final Answer:

   int matrix[4][4]; -> Option B

4. Quick Check:

   2D array syntax = int matrix[4][4]; [OK]

Hint: Use int matrix[rows][columns] for 2D arrays in C [OK]

Common Mistakes:

• Using single dimension array for matrix
• Using comma inside brackets (invalid syntax)
• Not specifying both dimensions

3. Given the following adjacency matrix for a graph with 3 nodes:

int matrix[3][3] = {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};

Which nodes are directly connected to node 1 (index 1)?

medium

A. [1, 2]

B. [0, 1]

C. [0, 2]

D. [2]

Solution

1. Step 1: Identify row for node 1

   Node 1 corresponds to index 1, so look at matrix[1]: {1, 0, 1}.

2. Step 2: Find indices with value 1

   Positions 0 and 2 have 1, meaning node 1 connects to nodes 0 and 2.

3. Final Answer:

   [0, 2] -> Option C

4. Quick Check:

   matrix[1][0] and matrix[1][2] = 1 [OK]

Hint: Check the row of the node for 1s to find connections [OK]

Common Mistakes:

• Confusing row and column indices
• Including the node itself as connected
• Reading zeros as connections

4. Consider this code snippet to initialize a 3x3 adjacency matrix in C:

int matrix[3][3];
for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++) {
    matrix[i][j] = 0;
  }
}
matrix[1][3] = 1;

What is the error in this code?

medium

A. Accessing out-of-bounds index matrix[1][3]

B. Missing semicolon after for loop

C. Incorrect initialization of matrix elements

D. Using wrong data type for matrix

Solution

1. Step 1: Check loop ranges and matrix size

   Matrix is 3x3, so valid indices are 0 to 2 for both rows and columns.

2. Step 2: Identify invalid index usage

   matrix[1][3] tries to access column index 3, which is out of bounds.

3. Final Answer:

   Accessing out-of-bounds index matrix[1][3] -> Option A

4. Quick Check:

   Index 3 invalid for size 3 array [OK]

Hint: Array indices go from 0 to size-1; check carefully [OK]

Common Mistakes:

• Ignoring array bounds and using invalid indices
• Assuming loops fix out-of-range errors
• Confusing row and column indices

5. You have a directed graph with 4 nodes. The adjacency matrix is:

int matrix[4][4] = {
  {0, 1, 0, 0},
  {0, 0, 1, 0},
  {1, 0, 0, 0},
  {0, 0, 0, 0}
};

Which nodes have no incoming edges?

hard

A. [0]

B. [0, 3]

C. [1, 3]

D. [3]

Solution

1. Step 1: Understand incoming edges in adjacency matrix

   Incoming edges to a node are shown by 1s in that node's column.

2. Step 2: Check each column for 1s

   Column 0 has 1 at row 2 (node 2 -> node 0).
   Column 1 has 1 at row 0 (node 0 -> node 1).
   Column 2 has 1 at row 1 (node 1 -> node 2).
   Column 3 has no 1s (all 0s).

3. Step 3: Identify nodes with no incoming edges

   Nodes 1 and 3 have no incoming edges because column 1 has 1 at row 0 (so node 1 has incoming edge), so this is incorrect. Actually, column 1 has 1 at row 0, so node 1 has incoming edge. Column 3 has no 1s, so node 3 has no incoming edges. Node 0 has incoming edge from node 2. Node 2 has incoming edge from node 1. So only node 3 has no incoming edges.

4. Final Answer:

   [3] -> Option D

5. Quick Check:

   Column 3 all 0s [OK]

Hint: Look down columns to find incoming edges for each node [OK]

Common Mistakes:

• Checking rows instead of columns for incoming edges
• Confusing directed and undirected edges
• Missing edges from nodes to themselves