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

Time Complexity: Graph Terminology Vertices Edges Directed Undirected Weighted

O(E)

Understanding Time Complexity

Graphs are made of points and connections. We want to understand how the work grows when we look at all points and connections.

How does the number of points and connections affect the time to explore or use the graph?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple graph traversal example
void printEdges(int vertices, int edges[][2], int edgeCount) {
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        printf("Edge from %d to %d\n", u, v);
    }
}
    

This code prints all edges in a graph represented by an edge list.

Identify Repeating Operations

• Primary operation: Loop over all edges to print each connection.
• How many times: Exactly once for each edge in the graph.

How Execution Grows With Input

As the number of edges grows, the work grows directly with it.

Input Size (edges)	Approx. Operations
10	10 print operations
100	100 print operations
1000	1000 print operations

Pattern observation: The work grows in a straight line with the number of edges.

Final Time Complexity

Time Complexity: O(E)

This means the time to process the graph grows directly with the number of edges.

Common Mistake

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

[OK] Correct: Edges represent connections, and many operations must look at each edge, so ignoring edges misses the real work.

Interview Connect

Understanding how vertices and edges affect time helps you explain graph problems clearly and choose the right approach confidently.

Self-Check

"What if the graph is directed versus undirected? How would that affect the time complexity of traversing all edges?"