The Hamiltonian Path problem (HP) accepts a graph G and returns whether or not G has a path that contains every vertex. The Hamiltonian Cycle problem (HC) accepts a graph G and returns whether or not G has a cycle that contains every vertex. 1. What is the worst-case time complexity of the reduction below when using an adjacency matrix to represent the graph? Show your work. In this reduction, HC is an algorithm that solves the Hamiltonian Cycle problem.

1. What is the worst-case time complexity of the reduction below when using an adjacency matrix to represent the graph? Show your work. In this reduction, HC is an algorithm that solves the Hamiltonian Cycle problem.

Input: G = (V, E): graph with n vertices and m edges Input: n, m: order and size of G Output: whether G has a Hamiltonian Path 1 Algorithm: HamiltonianReductiorn if HC(G) then 3return true end 5 for i1 to n-1 do efor j-i1 to n do if not G.isAdjacent(i, j) then G.AddEdge(i, j) if HC(G) then 10 return true end G.RemoveEdge(i, j) 12 13 14 end 15 end 16 return false end