Worst case time complexity of an algorithm reduction:

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 3 4 end 5 for i -1 to n-1 do 6for j-i+1 to n do return true if not G.isAdjacent(i, j) then 7 8 9 10 G.AddEdge(i. j) if HC(G) then return true end G.RemoveEdge(i. J) 12 13 14end 15 end 16 return false end 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 3 4 end 5 for i -1 to n-1 do 6for j-i+1 to n do return true if not G.isAdjacent(i, j) then 7 8 9 10 G.AddEdge(i. j) if HC(G) then return true end G.RemoveEdge(i. J) 12 13 14end 15 end 16 return false end