Description
Develop an upper bound for the complexity of the algorithm below, assuming
that G is represented using an adjacency list and H is represented using an
adjacency matrix. Justify your bound.
Input: G = (V, E): graph to analyze
Input: n, m: order and size of G
Output: H: graph with n vertices where the neighbors of each vertex
are those of distance one or two in G
1 Algorithm: ExpandedNeighborhood
2 H = Graph(n)
3 for v ∈ V do
4 for u ∈ NG(v) do
5 H.AddEdge(v, u)
6 for w ∈ NG(u) do
7 H.AddEdge(v, w)
8 end
9 end
10 end
11 return H
1