A graph G has n vertices and e edges. What are the worst-case time…

Concept

In graph traversal, running time is obtained by counting the vertex records and neighbor entries that the representation forces the algorithm to inspect.

An adjacency list stores only present adjacencies, whereas an n × n adjacency matrix reserves one cell for every ordered vertex pair.

Application

1. For a complete traversal, BFS starts again from each still-unvisited component. Across the whole graph, enqueue, dequeue, and visited-array work touches n vertices, contributing O(n).

2. With adjacency lists, every list is scanned once. The total number of stored adjacency entries is e for a directed graph and 2e for an undirected graph, so neighbor scanning is O(e). Together with vertex work, the bound is O(n + e).

3. With an adjacency matrix, processing one vertex requires scanning its row of n cells. Repeating this for n vertices inspects n × n cells, giving O(n2); the O(n) queue work is dominated.

Cross-check

If e = 0, a graph with n isolated vertices still requires O(n) work for a complete traversal, so O(e) alone is not the general adjacency-list bound. If the graph is dense and e = Θ(n2), O(n + e) becomes O(n2), consistent with the matrix bound.

Contrast

• O(e2), O(n2) assumes repeated edge-list passes that standard BFS does not perform.

• O(n) for every representation omits the required neighbor-entry or matrix-row scans.

• O(ne) for both representations assumes every vertex scans all edge records, which is not how adjacency-list BFS is organized.

Result

Therefore, the worst-case bounds are O(n + e) with adjacency lists and O(n2) with an adjacency matrix.