Weighted graphs in Data Structures Theory - Time & Space Complexity

Time Complexity: Weighted graphs

O(E)

Understanding Time Complexity

When working with weighted graphs, it is important to understand how the time to process the graph grows as the graph gets bigger.

We want to know how the number of steps changes when the graph has more nodes and edges.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function sumWeights(graph) {
  let total = 0;
  for (let node in graph) {
    for (let edge of graph[node]) {
      total += edge.weight;
    }
  }
  return total;
}
    

This code adds up all the weights of edges in a weighted graph represented as an adjacency list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding edge weights inside the inner loop.
• How many times: Once for every edge in the graph.

How Execution Grows With Input

As the number of edges increases, the total steps increase roughly the same amount.

Input Size (Edges)	Approx. Operations
10	About 10 additions
100	About 100 additions
1000	About 1000 additions

Pattern observation: The work grows directly with the number of edges.

Final Time Complexity

Time Complexity: O(E)

This means the time to sum weights grows in direct proportion to the number of edges in the graph.

Common Mistake

[X] Wrong: "The time depends mostly on the number of nodes, not edges."

[OK] Correct: Because edges hold the weights, the code must look at each edge, so the number of edges controls the time.

Interview Connect

Understanding how time grows with edges and nodes helps you explain graph algorithms clearly and confidently in interviews.

Self-Check

"What if the graph was represented as an adjacency matrix instead of a list? How would the time complexity change?"