e() removes an element from Q. following procedure whose input is an undirected grap LIST. weight (vi, vj) is a positive weight assigned to e Hure Proc1 (G) _lize(); h vertex v₂ € V(G) do each edge (v₁, vj) incident on v, do w← weight(vi, vj); Q.Insert (w); 1 (Q.IsNotEmpty()) do - Q.Delete (); at w;
e() removes an element from Q. following procedure whose input is an undirected grap LIST. weight (vi, vj) is a positive weight assigned to e Hure Proc1 (G) _lize(); h vertex v₂ € V(G) do each edge (v₁, vj) incident on v, do w← weight(vi, vj); Q.Insert (w); 1 (Q.IsNotEmpty()) do - Q.Delete (); at w;
Related questions
Question
Please show steps clearly
Transcribed Image Text:1. Let Q be an implementation of some data structure where:
Q.Initialize() and Q.IsNotEmpty() take ✪(1) time. Initially, Q has 0 elements.
Q.Insert() takes (log₂ (s)) time where s is the number of elements in Q.
Q.Insert() adds one element to Q.
●
●
• Q.Delete() takes (s) time where s is the number of elements in Q.
Q.Delete() removes an element from Q.
Consider the following procedure whose input is an undirected graph G. Edges of G are represented by
an adjacency LIST. weight(vį, vj) is a positive weight assigned to edge (vi, Vj).
procedure Proc1 (G)
1 Q.Initalize();
2 foreach vertex v₁ € V(G) do
3
4
5
foreach edge (vi, vj) incident on vi do
D
w ← weight(vi, vj);
Q.Insert (w);
end
6
7 end
8 while (Q.IsNotEmpty()) do
9
w
Q.Delete ();
10
Print w;
11 end
Let n be the number of vertices of G and let m be the number of edges of G.
(a) Analyze lines 1-7 of Proc1 giving a bound on their asymptotic running time in terms of n and m.
(b) Analyze lines 8-11 of Proc1 giving a bound on their asymptotic running time in terms of n and m.
(c) Give the asymptotic running time of Proc1 in terms of n and m.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
