Adjacency List Representation in DSA C - Time & Space Complexity

Time Complexity: Adjacency List Representation

O(n + e)

Understanding Time Complexity

We want to understand how the time to build and use an adjacency list changes as the graph grows.

How does the number of nodes and edges affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Create adjacency list for graph with n vertices and edges array
void createAdjList(int n, int edges[][2], int edgesCount, List adjList[]) {
    for (int i = 0; i < n; i++) {
        adjList[i] = createEmptyList();
    }
    for (int i = 0; i < edgesCount; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        addToList(adjList[u], v);
        addToList(adjList[v], u); // for undirected graph
    }
}
    

This code builds an adjacency list for an undirected graph by adding each edge to the lists of both connected nodes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over all edges to add connections.
• How many times: The loop runs once for each edge, twice adding nodes to lists.

How Execution Grows With Input

As the number of edges grows, the work grows roughly twice as fast because each edge adds two entries.

Input Size (edgesCount)	Approx. Operations
10	About 20 additions to lists
100	About 200 additions to lists
1000	About 2000 additions to lists

Pattern observation: The operations grow linearly with the number of edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time grows linearly with the number of nodes plus the number of edges.

Common Mistake

[X] Wrong: "The time depends only on the number of nodes (n)."

[OK] Correct: The edges (connections) also matter because each edge adds work to the lists.

Interview Connect

Understanding adjacency list complexity helps you explain graph storage and traversal efficiency clearly in interviews.

Self-Check

"What if the graph was directed and we only added one direction per edge? How would the time complexity change?"