Graph representations (adjacency matrix vs list) in Data Structures Theory - Performance Comparison

Time Complexity: Graph representations (adjacency matrix vs list)

O(n) for adjacency matrix, O(degree(i)) for adjacency list

Understanding Time Complexity

When working with graphs, how we store connections affects how fast we can check or find neighbors.

We want to know how the time to do these tasks grows as the graph gets bigger.

Scenario Under Consideration

Analyze the time complexity of checking all neighbors of a node using two common graph storage methods.

// Adjacency Matrix
for (int j = 0; j < n; j++) {
  if (matrix[i][j] == 1) {
    // process neighbor j
  }
}

// Adjacency List
for (int neighbor : list[i]) {
  // process neighbor
}
    

This code checks all neighbors of node i using either a matrix or a list.

Identify Repeating Operations

Look at what repeats when finding neighbors of one node.

• Primary operation: Looping through possible neighbors.
• How many times: For matrix, loops n times; for list, loops degree(i) times (number of actual neighbors).

How Execution Grows With Input

As the graph grows, the matrix always checks all nodes, but the list only checks actual neighbors.

Input Size (n)	Adjacency Matrix Ops	Adjacency List Ops
10	10 checks	degree(i) checks (e.g., 3)
100	100 checks	degree(i) checks (e.g., 5)
1000	1000 checks	degree(i) checks (e.g., 10)

Pattern observation: Matrix cost grows with total nodes, list cost grows with actual neighbors.

Final Time Complexity

Time Complexity: O(n) for adjacency matrix, O(degree(i)) for adjacency list

This means matrix always checks all nodes, while list only checks real neighbors, making it faster for sparse graphs.

Common Mistake

[X] Wrong: "Adjacency matrix is always faster because it uses a simple 2D array."

[OK] Correct: Matrix checks every node even if no connection exists, so it can be slower when many nodes have few neighbors.

Interview Connect

Understanding these differences helps you choose the right graph storage for your problem and explain your choice clearly.

Self-Check

"What if the graph is dense, meaning most nodes connect to many others? How would the time complexity for adjacency list compare to adjacency matrix?"