Q. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?

(A) o(n!)
(B) o(n! * n)
(C) o(log n)
(D) o(n)

💬 Discuss

✅ Correct Answer: (B) o(n! * n)

Explanation: for a graph having n vertices traverse the permutations in n! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes n iterations (i.e.) o(n! * n).

Published by Mr. Dubey ⭐ 111.54K Points at 16-Sep-2023 03:44 pm in Design and Analysis of Algorithms

Explanation by: Mr. Dubey

for a graph having n vertices traverse the permutations in n! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes n iterations (i.e.) o(n! * n).

💬 Discussion

📊 Question Analytics

👁️

797

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

90%

Success Rate

Q. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?

Explanation by: Mr. Dubey

💬 Discussion

Related MCQs

📊 Question Analytics