4. [15 points/ Consider the following procedure (Procl(G)) whose input is an und

Question

4. [15 points/ Consider the following procedure (Procl(G)) whose input is an undirected graph G. Edges of G are represented by an adjacency LIST. procedure Proc1(G) 1 Q.Init) 2 foreach vertex vi E V(G) do 3foreach edge (vi, vj) incident on vi do Q is a priority queue implemented as a Min-heap */ foreach vertex vp E V(G) do 80; foreach edge (vp, va) incident on vp do 5 6 if (ty = v.) then 8 end 10 end Q.Insert(s); end 12 13 end 14 end What is the maximum size of the priority queue Q? Analyze the running time of this algorithm in terms of the number of vertices n = |v| and the number of edges m2-IEI. (Justify your answer. Do not simply give a running time.)

Explanation / Answer

Minimum size of the priority queue Q = n-1

Where n = number of nodes.

Time Complexity:

             for each vertex the time complexity will be log|V| = log(n)

             for each edge the time complexity will be log|E| = log(m)

             Again and again it will be in loop ,

           Therefore, the time complexity = log|V+E| = log(n+m).

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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