Hello, I\'m working on the Traveling Salesman Problem and I\'ve done research on

Question

Hello, I'm working on the Traveling Salesman Problem and I've done research on the internet and read about different solutions and found that the time complexity is O(n!) for the "brute force" way of solving the problem. The formula that I got to calculate the number of different tours was (n!)/2, so if there were only 3 cities, then there would be 3 different tours. I drew out examples/tours to find this. But the question I'm trying to solve is based on an algorithm written in pseudo code.

Any help is appreciated, thank you!

Explanation / Answer

First of all ...we can calculate complexity of given below code

for all possible tours, do: ---------------> n( since it checks false statement too)
find the length of the tour --------> n -1
if length < min ----------------------> n-1
min = length ----------------> depends on above if condition ..which may be some n-1(let us assume)
store tour ----------------> depends on above if condition ..which may be some n-1(let us assume)

so total complexity is: n + n-1 + n-1 + n -1 + n-1
= 5n-4
in terms of big oh ....O(5n-4) ==>we can eliminate 4 ===>O(5n) ====>O(n)

So, O(n) and not O(n!)

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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