Time complexity of adjacency list representation?

Question

I am going through this link for 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)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", 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

Slackjawed

Suppose the graph has no edges. How long does the algorithm take? – Goldthread

@Goldthread We have to check or scan every vertex once, right ? But It is a nested loop so shouldn't time complexity be like that ? – Slackjawed

Answer 1

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.

Acerose

If there is an outer loop of n iterations then the time complexity should be O(V * E) right? what am I missing here? – Endstopped

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) – Acerose

@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. – Canner