Let G = (V, E) be an undirected, connected graph with n vertices and m edges. Al

Question

Let G = (V, E) be an undirected, connected graph with n vertices and m edges. All vertices .ire initially un-marked. Consider the following algorithm: Algorithm traverse(G, u) Input: Undirected, connected graph G. and vertex u of G Mark u c leftarrow 0 For each edge (u, v) incident on u do {For each vertex w of G do c leftarrow c + 1 if v is not marked then c leftarrow c + traverse(G, v)} return c Assume that G is stored in an adjacency list. What is the time complexity of the above algorithm in the worst case? O(m) O(n + m) O(n^2) O(nm) O(n^3) Consider the following graph. Assume that we use Dijkstra's algorithm to find shortest paths from vertex s to the other vertices in the graph. In which order are the final distance Labels u.d computed? (Or in other words, in which order are the shortest paths computed?) s, 1, 2, 4, 3, 5 s, 1, 2, 3, 4, 5 s, 1, 2, 4, 5, 3 s, 1, 4, 2, 3, 5 8, 1, 4, 3, 2, 5

Explanation / Answer

The complexity of the following algorithm is o(n^2) as there are 2 for loop so the inner loop will we executed n square times. Hence the complexity of the algorithm given is o(n^2)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.