The problem asks for creating the adjacency list of a graph which contains only the edges that are present in both graphs (they have the same number of vertices). I have come up with this algorithm written in pseudocode for which I cannot determine the time complexity (best case, worst case). After thinking a lot, I believe I cannot even say which is the best case or the worst case.
for i <- 1,v do
for v in adj1[i] do
found <- false
for u in adj2[i] do
if (u=v) then
found = true
break
endif
endfor
if (found) then
adj_int[i].push_back(v)
endif
endfor
endfor
What is the time complexity of this algorithm? Let V=number of vertices, E1=number of edges from graph1 and E2=number of edges from graph2.