The three for loops are nested Consider the following function whose input is an

Question

The three for loops are nested

Consider the following function whose input is an undirected graph G. Edges of G are represented by an adjacency LIST.

procedure func1(G)

1 s 0;

2 foreach vertex vi V (G) do

3 foreach edge (vi , vj ) incident on vi do

4 foreach vertex vp V (G) do

5 if (vj = vp) then

6 s s + 1;

7 end

8 end

9 end

10 end

11 return (s);

Let n be the number of vertices of G and let m be the number of edges of G. Analyze the running time of Function func1, giving a bound on its asymptotic running time in terms of n and m.

Explanation / Answer

Solution :

After analyzing, the running time of function func1 is O(m log n).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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