Adjacency List Representation in DSA Typescript - Time & Space Complexity

Time Complexity: Adjacency List Representation

O(n + e)

Understanding Time Complexity

We want to understand how fast we can access and traverse a graph stored as an adjacency list.

How does the time to visit nodes and edges grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Traverse all nodes and their neighbors in an adjacency list
function traverseGraph(adjList: Map<number, number[]>) {
  for (const node of adjList.keys()) {
    const neighbors = adjList.get(node) || [];
    for (const neighbor of neighbors) {
      // process edge from node to neighbor
    }
  }
}
    

This code visits every node and then visits each neighbor connected to that node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The nested loops: outer loop over all nodes, inner loop over each node's neighbors.
• How many times: Outer loop runs once per node (n times), inner loop runs once per edge connected to that node.

How Execution Grows With Input

As the graph grows, the number of nodes (n) and edges (e) increase.

Input Size (n nodes, e edges)	Approx. Operations
10 nodes, 15 edges	About 10 (nodes) + 15 (edges) = 25 operations
100 nodes, 200 edges	About 100 + 200 = 300 operations
1000 nodes, 5000 edges	About 1000 + 5000 = 6000 operations

Pattern observation: The total work grows roughly with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time to traverse depends on how many nodes and edges the graph has combined.

Common Mistake

[X] Wrong: "Traversal time is just O(n) because we visit each node once."

[OK] Correct: We also visit all edges connected to nodes, so edges add to the total work and cannot be ignored.

Interview Connect

Understanding adjacency list traversal time helps you explain graph algorithms clearly and shows you know how data size affects performance.

Self-Check

"What if the graph was stored as an adjacency matrix instead? How would the time complexity change?"