Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Typescript - Time & Space Complexity

Time Complexity: Graph Terminology Vertices Edges Directed Undirected Weighted

O(V + E)

Understanding Time Complexity

Graphs are made of points and connections. We want to understand how the work grows when we explore these connections.

How does the number of points and connections affect the time to visit or check them?

Scenario Under Consideration

Analyze the time complexity of this simple graph traversal code.

function traverseGraph(graph: Map): void {
  for (const vertex of graph.keys()) {
    const edges = graph.get(vertex) || [];
    for (const neighbor of edges) {
      // process edge from vertex to neighbor
    }
  }
}
    

This code visits every vertex and its connected edges once.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: Visiting each vertex and then each edge connected to it.
• How many times: Outer loop runs once per vertex (V times), inner loop runs once per edge connected to that vertex.

How Execution Grows With Input

As the graph grows, the work grows with the number of vertices and edges.

Input Size (V vertices, E edges)	Approx. Operations
10 vertices, 15 edges	~25 operations (10 + 15)
100 vertices, 200 edges	~300 operations (100 + 200)
1000 vertices, 5000 edges	~6000 operations (1000 + 5000)

Pattern observation: The total work grows roughly by adding vertices and edges together.

Final Time Complexity

Time Complexity: O(V + E)

This means the time to explore the graph grows with the total number of points plus connections.

Common Mistake

[X] Wrong: "The time depends only on the number of vertices."

[OK] Correct: Edges also matter because each connection must be checked, so ignoring edges misses part of the work.

Interview Connect

Understanding how vertices and edges affect time helps you explain graph algorithms clearly and confidently in interviews.

Self-Check

"What if the graph was directed instead of undirected? How would the time complexity change?"