The time complexities of four standard graph algorithms are listed below.…
2012
The time complexities of four standard graph algorithms are listed below. Here, n is the number of vertices and m is the number of edges.
Match each algorithm item with its complexity code.
Algorithm item | Algorithm | Complexity code | Time complexity |
|---|---|---|---|
a | Bellman–Ford algorithm | 1 | O(m log n) |
b | Kruskal’s algorithm | 2 | O(n3) |
c | Floyd–Warshall algorithm | 3 | O(mn) |
d | Topological sorting | 4 | O(n + m) |
Answer: A. a b c d 3 1 2 4 — ConceptAn algorithm’s asymptotic time is determined by the dominant operation and how many times it is repeated as the graph grows. Scanning every edge across…
- A.
a
b
c
d
3
1
2
4
- B.
a
b
c
d
2
4
3
1
- C.
a
b
c
d
3
4
1
2
- D.
a
b
c
d
2
1
3
4
Show answer & explanation
Correct answer: A
Concept
An algorithm’s asymptotic time is determined by the dominant operation and how many times it is repeated as the graph grows.
Scanning every edge across a linear number of vertex passes gives O(mn); examining every ordered triple of vertices gives O(n3); a single vertex-and-edge traversal gives O(n + m).
Application
Bellman–Ford relaxes all m edges for at most n − 1 main passes. Its dominant work is therefore m(n − 1), which is O(mn), so a maps to 3.
Kruskal’s algorithm sorts the m edges and then performs near-linear disjoint-set operations. Sorting dominates: O(m log m), conventionally written as O(m log n) for a simple graph, so b maps to 1.
Floyd–Warshall uses three nested loops over the vertices—intermediate, source, and destination. This performs O(n3) work, so c maps to 2.
Topological sorting by DFS or Kahn’s algorithm processes each vertex and each edge a constant number of times. Its time is O(n + m), so d maps to 4.
Cross-check
The dominant-work pattern independently reproduces all four codes:
Algorithm | Dominant work | Code |
|---|---|---|
Bellman–Ford algorithm | Repeated full edge scans | 3 |
Kruskal’s algorithm | Sorting the edge list | 1 |
Floyd–Warshall algorithm | Three vertex loops | 2 |
Topological sorting | One vertex-and-edge traversal | 4 |
Therefore, the required matching is a–3, b–1, c–2, d–4.