Question

Question 6 15pt Given undirected positive edge weight graph G(V.E) and boo(m) = m3 while (v € VX for all u € Adj[v]) { boo(V): ) ) What is the run-time of the code above given the Graph is store as adj. list? What is the run-time of the code above given the Graph is store as adj. matrix? Please explain your answer.

Answer 1

SOL:

Run time of the above code if the graph is stored as adj List:

The adjaceny List representation time complexity is O(V+E)

see in the first step while(u∈V) we are checking whether u belongs to Vertex set V or not . so This loop runs for V times

In the for loop for all u ∈ Adj[v] we are checking whether u belongs to adj[v] or not The adj[v] means E entries in the adjacency list for every vertex V.

so for every one time of the outer loop inner loop runs for E times. For every V inner loop runs for E times

so how many times the both loops run together is O(VE)

The time complexity of bool(V) is O(V³) as given in the question

so total time complexity is O(VEV³)

Run time fotr the above code if graph is stored as adj matrix:

The time complexity for the graph is stored as adj matrix is O(V²)

see in the first step while(u∈V) we are checking whether u belongs to Vertex set V or not . so This loop runs for V times

In the for loop for all u ∈ Adj[v] we are checking whether u belongs to adj[v] or not The adj[v] means V entries in the adjacency list for every vertex V.

so for every one time of the outer loop inner loop runs for V times. For every V inner loop runs for V times

so how many times the both loops run together is O(V²)

The time complexity of bool(V) is O(V³) as given in the question

so total time complexity is O(V²V³) = O(V⁵)