Time complexity of this adjacency list-based algorithm which finds the common edges of two undirected graphs

Viewed 75

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.

0 Answers
Related