retagged by
1,202 views
1 votes
1 votes
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)
retagged by

1 Answer

1 votes
1 votes
  • 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)

Related questions

2 votes
2 votes
1 answer
3
Shubhanshu asked Apr 28, 2017
2,563 views
Given an adjacency-list representation of a directed graph, how long does it take to compute the out degree of every vertex? How long does it take to compute in-degrees?