CODEWITHSUNDEEP
algorithmtime-complexitybreadth-first-searchadjacency-list
Garrick
Garrick

Reputation: 689

Time complexity of adjacency list representation?

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

Upvotes: 11

Views: 27845

Answers (1)

Tobias Ribizel
Tobias Ribizel

Reputation: 5421

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.

Upvotes: 20

Related Questions