Adjacency List vs Matrix When to Choose Which in DSA C - 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

We want to understand how the time to check connections in a graph changes depending on how we store it.

Which storage method is faster for different tasks and graph sizes?

Scenario Under Consideration

Analyze the time complexity of checking if an edge exists between two nodes.

// Using adjacency matrix
int hasEdgeMatrix(int n, int matrix[n][n], int u, int v) {
    return matrix[u][v];
}

// Using adjacency list
int hasEdgeList(int u, int v, int* adj[], int sizes[]) {
    for (int i = 0; i < sizes[u]; i++) {
        if (adj[u][i] == v) return 1;
    }
    return 0;
}
    

This code checks if there is a direct connection (edge) between two nodes using two different graph storage methods.

Identify Repeating Operations

Look at what repeats when checking edges.

• Primary operation: For matrix, direct access; for list, loop through neighbors.
• How many times: Matrix does 1 check; list loops up to the number of neighbors of node u.

How Execution Grows With Input

Imagine the graph grows bigger with more nodes and edges.

Input Size (n)	Matrix Checks	List Checks (avg neighbors)
10 nodes	1 check	about 2-3 checks
100 nodes	1 check	about 5-10 checks
1000 nodes	1 check	about 10-20 checks

Matrix access stays the same no matter the size. List checks grow with how many neighbors a node has.

Final Time Complexity

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

This means matrix lets you check edges instantly, while list depends on how many neighbors the node has.

Common Mistake

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

[OK] Correct: Checking if an edge exists can be slower with lists if a node has many neighbors, because you must look through them one by one.

Interview Connect

Knowing when to use adjacency lists or matrices shows you understand trade-offs in data structures, a key skill in problem solving.

Self-Check

What if the graph is very dense (almost every node connected to every other)? How would the time complexity of adjacency list checks compare to adjacency matrix?