Question

PROMPT:

Consider a graph G. A connected component is a maximal subset of nodes that induces a connected sub graph. It’s maximal in the sense that you cannot add a node with the resulting induced sub graph remaining connected.The following function numComponents returns the number of connected components in an undirected graph.

int numComponents(int numNodes, struct ListNode *adjList) enum Boolean visited[numNodes]; for (int k-0; k<numNodes; k++){ // visited[k] indicates whether node k was visited visited false; int queue[numNodes]; int numComp = 0; for (int k=0; k«numNodes; k++) { // Queue used to store nodes // Number of connected components if (visited[k]false) // Unvisited node, so it's the start of a new component numComp++; int head 0 int tail0 int size 1 queue[tail]k; visited[k] true; while (size>0)/Do a breadth-first-search to all unvisited nodes // Initialize the queue by putting node k in it // head, tail, and size of the queue II // Insert nodek int current queue[head+t]; size for (struct ListNode *p = adjust[current]; p != NULL; p=p->next) { if (visited[p->nodelD]false)Node p->nodelD hasn't been visited // tail++; queue[tailp->nodelD; size++ visited[p->nodelD] true; Put the node in the queue // The node has been visited return numComp;

QUESTION:

What is the time complexity for this function? The time complexity should be a function of the number of nodes |V| and the number of edges |E|.

Answer 1

Constant time operations are not considered while calculating the time complexity.

you should concentrate on loops for checking the time complexity.

The first loop runs number of node times so it's complexity is O(V) where V is number of nodes.

this will be considered

Next for loop is outer for loop which again runs O(V) times

BFS deals with removing one element from the queue and appending further elements with queue. this has O(V²) complexity if adjacency matrix is used. if adjacency list is used, complexity is O(V+E). means that whichever is higher will dominate.

We use a list in our case so the complexity is O(V+E).

this is inner loop complexity. total complexity is inner loop complexity * outer loop complexity

= O(V*(V+E))

To find the complexity of the function, add O(V) + O(V(V+E))

now complexity = O(V) + O(V² + VE)

since higher order terms are present lower order terms can be ignored.

complexity is O(V² + VE)