Assuming that this graph is stored in an adjacency list. What would the time complexity be and how would we determine it in the worst case?

Question

Let G = (V, E) be an undirected, connected graph with n vertices and m > n edges. All vertices are initially un-marked and they are stored in an array V . Consider the following algorithm:

Algorithm traversal(G)
Input: Undirected, connected graph G.
c←0
for i ← 0 to n − 1 do {
     u ← V [i]
     for each edge (u, v) incident on u do {
           Mark u
           if v is not marked then c ← c + 1 }
}

Assume that G is stored in an adjacency list. What is the time complexity of algorithm traverse(G) in the worst case? These are the options. (A) O(n) (B) O(n2) (C) O(n × degree(u)) (D) O(m) (E) O(nm) Basically this is a practice question for one of my tests, We haven't been given the answer sheet yet. I initially thought the answer would be c) O(n x degree(u)). I thought this because I know the incident method on a adjacency list has time complexity O(degree(u)) and your doing it n times because of the for loop. However, other people have indicated they think it is O(nm) thus im wondering which is correct and how you would determine it.

I initially thought the answer would be c) O(n x degree(u)). I thought this because I know the incident method on a adjacency list has time complexity O(degree(u)) and your doing it n times because of the for loop.

Answer 1

You mark a vertex and increase c once for each edge. Therefore, the time complexity of your algorithm is O(m), because m > n.

Also, you can reason about it in the other way. Each iteration of the inner loop has complexity O(degree(u_i)), where u_i is the i-th vertex of the graph. Then the whole algorithm has complexity O(n) + \sum_i O(degree(u_i)), or a sum of all degrees of the vertices, or, equivalently, O(m).