PLEASE SOLVE ALL FOR THUMBS UP

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 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: HamiltonianReduction 2 if HC(G) then 3return true 4 end 5for i 1 to n _ 1 do for j = i + 1 to n do 7 if not G.isAdjacent (i, j) then G.AddEdge(i, j) if HC(G) then return true 10 G.RemoveEdge(i, j) end 12 13 14end 15 end 16 return false For questions 2-4, decide whether HamiltonianReduction allows you to conclude something about the problem complexity for HC based on on information about HP or vice versa. If so, indicate what you can conclude If not, indicate that "nothing can be concluded. Justify your answer 2. HP is O(n22") 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 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: HamiltonianReduction 2 if HC(G) then 3return true 4 end 5for i 1 to n _ 1 do for j = i + 1 to n do 7 if not G.isAdjacent (i, j) then G.AddEdge(i, j) if HC(G) then return true 10 G.RemoveEdge(i, j) end 12 13 14end 15 end 16 return false For questions 2-4, decide whether HamiltonianReduction allows you to conclude something about the problem complexity for HC based on on information about HP or vice versa. If so, indicate what you can conclude If not, indicate that "nothing can be concluded. Justify your answer 2. HP is O(n22")