# Time complexity of adjacency list representation?

http://www.geeksforgeeks.org/graph-and-its-representations/

I have a simple doubt in some part of a code as follows :

``````// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
``````

Since, here for every `V` while loop is executed say `d` times where d is the degree of each vertex.

So, I think time complexity is like

``````d0 + d1 + d2 + d3 ....... +dV where di is the degree of each vertex.
``````

All this sums up O(E), but the link says that time complexity is O(|V|+|E|)

Not sure what is the problem with the understanding. Some help needed here

• Suppose the graph has no edges. How long does the algorithm take? Commented Jul 8, 2017 at 6:57
• @user2357112 We have to check or scan every vertex once, right ? But It is a nested loop so shouldn't time complexity be like that ? Commented Jul 8, 2017 at 6:59

The important thing here is that for the time complexity to be valid, we need to cover every possible situation:

• The outer loop is executed O(|V|) regardless of the graph structure.
• Even if we had no edges at all, for every iteration of the outer loop, we would have to do a constant number of operations (O(1))
• The inner loop is executed once for every edge, thus O(deg(v)) times, where deg(v) is the degree of the current node.
• Thus the runtime of a single iteration of the outer loop is O(1 + deg(v)). Note that we cannot leave out the 1, because deg(v) might be 0 but we still need to do some work in that iteration
• Summing it all up, we get a runtime of O(|V| * 1 + deg(v1) + deg(v2) + ...) = O(|V| + |E|).

As mentioned before, |E| could be rather small such that we still need to account for the work done exclusively in the outer loop. Thus, we cannot simply remove the |V| term.

• If there is an outer loop of n iterations then the time complexity should be O(V * E) right? what am I missing here? Commented Dec 29, 2020 at 15:34
• The total number of edges E is only a veeeery pessimistic upper bound for the amount of work you do in a single iteration of the loop. You can do much better by noticing that we look at only `degree(v)` outgoing edges for each vertex v, plus some additional constant work (reading the head pointer for v). The sum of all degrees is two times the number of edges. Thus in total, we only need a constant amount of work per vertex and edge (as summarized in the last bullet point) Commented Dec 29, 2020 at 19:50
• @MidhunrajRPillai it is not an outer loop over all V and inner loop over all E. The inner loop is over the degree of each edge which is not a constant. Commented Oct 3, 2022 at 1:23
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}