Adjacency Matrix Representation in DSA Typescript - Time & Space Complexity

Time Complexity: Adjacency Matrix Representation

O(n²)

Understanding Time Complexity

We want to understand how the time to check or build connections in a graph grows as the graph gets bigger.

How does the number of nodes affect the work done using an adjacency matrix?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function printAdjacencyMatrix(matrix: number[][]): void {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(`Edge from ${i} to ${j}: ${matrix[i][j]}`);
    }
  }
}
    

This code prints all edges in a graph represented by an adjacency matrix of size n x n.

Identify Repeating Operations

• Primary operation: Nested loops over the matrix rows and columns.
• 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 n grows, the total operations grow by n squared because we check every possible pair of nodes.

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

Pattern observation: Doubling the number of nodes roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n²)

This means the time to process the adjacency matrix grows with the square of the number of nodes.

Common Mistake

[X] Wrong: "Checking all edges in an adjacency matrix is a quick, linear operation."

[OK] Correct: Because the matrix has n rows and n columns, you must check n x n entries, so the work grows much faster than just n.

Interview Connect

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

Self-Check

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