1. What is the worst-case time complexity of the reduction below when using an a

Question

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 sreturn true 4 end s fori 1 to n 1 do 6 for 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 end 14end 15 end 16 return false

Explanation / Answer

Answer :

Here we are using Hamiltonian Cycle and thw worst case complexity for the hamiltonian is O(N!) and here nested for loops are used so the worst time complexity of nested loops is equal to the number of times the innermost statement are executed.

So. it is O(n2) .

Final Complexitiy are: O(n2) + O(N!)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.