Question

In what time can the Hamiltonian path problem can be solved using dynamic programming?

(a) O(N)

(b) O(N log N)

(c) O(N^2)

(d) O(N^2 2^N)

The question was posed to me in an international level competition.

My enquiry is from Checksum, Complexity Classes & NP Complete Problems in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

Correct option is (d) O(N^2 2^N)

The best explanation: Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N^2 2^N).