Why Graphs Exist and What Trees Cannot Model in DSA Typescript - Performance Analysis

Time Complexity: Why Graphs Exist and What Trees Cannot Model

O(n + e)

Understanding Time Complexity

We want to understand why graphs are needed beyond trees and how this affects the time to process connections.

How does the complexity of handling graphs compare to trees?

Scenario Under Consideration

Analyze the time complexity of traversing a graph compared to a tree.

function traverseGraph(adjList: Map, start: number): void {
  const visited = new Set();
  const stack = [start];
  while (stack.length > 0) {
    const node = stack.pop()!;
    if (!visited.has(node)) {
      visited.add(node);
      for (const neighbor of adjList.get(node) || []) {
        stack.push(neighbor);
      }
    }
  }
}
    

This code visits all nodes reachable from a start node in a graph using depth-first search.

Identify Repeating Operations

Look for loops and repeated visits.

• Primary operation: Visiting each node and exploring its neighbors.
• How many times: Each node and each edge is processed once during traversal.

How Execution Grows With Input

As the number of nodes and edges grows, the work grows with both.

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

Pattern observation: Operations grow roughly with the sum of nodes and edges, not just nodes like in trees.

Final Time Complexity

Time Complexity: O(n + e)

This means the time to traverse depends on both the number of nodes and the number of edges in the graph.

Common Mistake

[X] Wrong: "Graphs are just like trees, so traversal time depends only on nodes."

[OK] Correct: Graphs can have many connections (edges) between nodes, so edges add to the work done.

Interview Connect

Understanding how graphs differ from trees and their traversal costs helps you explain data structure choices clearly and confidently.

Self-Check

What if the graph is very dense, with edges close to the maximum possible? How would that affect the time complexity?