Adjacency List vs Matrix When to Choose Which in DSA Typescript - Complexity Comparison

Time Complexity: Adjacency List vs Matrix When to Choose Which

O(1) for adjacency matrix, O(k) for adjacency list

Understanding Time Complexity

Choosing between adjacency list and adjacency matrix affects how fast graph operations run.

We want to know how the time to check or add edges changes as the graph grows.

Scenario Under Consideration

Analyze the time complexity of checking if an edge exists in two graph representations.

// Using adjacency matrix
function hasEdgeMatrix(matrix: number[][], u: number, v: number): boolean {
  return matrix[u][v] === 1;
}

// Using adjacency list
function hasEdgeList(list: number[][], u: number, v: number): boolean {
  return list[u].includes(v);
}
    

This code checks if there is an edge from node u to node v using two different graph storage methods.

Identify Repeating Operations

Look at what repeats when checking edges.

• Primary operation: For matrix, direct access; for list, searching through neighbors.
• How many times: Matrix access is once; list search depends on number of neighbors of u.

How Execution Grows With Input

How does checking edges grow as graph size grows?

Input Size (n nodes)	Matrix Accesses	List Searches (neighbors)
10	1	Up to 9
100	1	Up to 99
1000	1	Up to 999

Matrix access stays constant; list search grows with number of neighbors, which depends on graph density.

Final Time Complexity

Time Complexity: O(1) for adjacency matrix, O(k) for adjacency list

This means matrix checks edges instantly, while list checks take time proportional to neighbors count.

Common Mistake

[X] Wrong: "Adjacency list is always faster than matrix because it uses less space."

[OK] Correct: List uses less space but edge checks can be slower if many neighbors exist, unlike constant-time matrix access.

Interview Connect

Understanding these differences helps you pick the right graph storage for fast operations in real problems.

Self-Check

"What if the graph is very sparse? How does that affect the choice between adjacency list and matrix for edge checks?"