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-it!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 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(n"2") 3. HC is O(n22) 4. HP is 2(n2 lgn)

Explanation / Answer

Solution:

1)

There are two loops nested in the given code

so the run of the inner loop will go like this

1, 2, 3, 4, 5, ....n

effective running tme will be sum of these

which is n(n+1)/2 = O(n^2)

T(n)= O(n^2)

2)

cannot be concluded

3)

True

4)

cannot be concluded.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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