Time Complexity of Printing a Graph in Adjacency List Representation-CodePudding

What is the order of growth of the running time of the following code if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?

// G.V() returns number of vertices, G is the graph. 
for (int v = 0; v < G.V(); v  ) {
    for (w : G.adj(v)) {
        System.out.println(v   "-"   w); 
    }
}

Why is the time complexity of the above code Theta(V E), where V is the number of vertices and E is the number of edges?

I believe that if we let printing be the cost function, then it should be Theta(sum of degrees of each v) = Theta(2E) = Theta(E) because we enter the inner loop deg(v) times for vertex v.

CodePudding user response：

if we let printing be the cost function, then

Using such assumption, yes, there will be Theta(E) println calls.

However, generally the execution time does not depend only on printing, but also on other instructions such as v , there will be Theta(V E) of them all.

CodePudding user response：

for (i = 0; i < array1.length; i  ) {
    for (j = 0; j < array2.length; j  ) {
        //Do something
    }    
}

What is the time complexity?

O(array1.length * array2.length)

Same is your case. Just that those loops are in context of graph, vertices and edges.

O(number of vertices * number of edges).

"Sum of all degrees is equal to twice the number of edges" is correct. Though, doesn't have anything to do with the code you posted.