Algorithms

Question

Consider the following fragment of code for a graph algorithm on an undirected graph.

 

for each vertex i in V

     mark i as visited

     for each edge (j,i) pointing into i

           update weight(j,i) to weight(j,i) + k

Which of the following is the most accurate description of the complexity of this fragment. (Recall that n is the number of vertices, m is the number of edges.)

(a) O(n)

(b)O(nm)

(c)O(n+m)

(d)O(m)

Answer 1

• The code runs for each vertex. Thus outer loop should run for n times.
• In worst case there may be  a vertex to which all edges are falling. In that case inner loop will run  m times.
•  The algorithm may run nm times.

The complexity should be O(nm)

Comments

Yes, because an edge can fall to only to maximum 2 vertices (being an undirected graph)

---

Consider a complete graph say K₅...... for each vertex say

v1, all other vertex v2,v3,v4,v5 will be updated....then for

vertex v2, ....v1,v3,v4,v5 will be updated

and so on for v3,v4,v5

there fore it should be O(mn)..... am i wrong?

---

@Vasu yes. There also answer is $O(m+n)$ just that $m= n^2$ being a complete graph. Basically we run the algorithm for each edge and hence need to consider only the number of edges assuming a connected graph.