A

Admin • 833K Points
Coach

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)

Explanation by: Admin

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).

You must be Logged in to update hint/solution

Discusssion

Login to discuss.

Be the first to start discuss.