# Calculate the time complexity for the following Travelling Salesman problem algorithm

Consider the following algorithm for solving the TSP:

$n$ = number of cities

$m$ = $n\times n$ matrix of distances between cities

min = (infinity)

for all possible tours, do:
find the length of the tour
if length < min
min = length
store tour


What is the complexity of this algorithm in terms of $n$(the number of cities)? You may assume that matrix lookup is $O(1)$, and that the body of the if-statement is also $O(1)$. You need not count the if-statement or the for-loop guard(ie. conditional)checks, etc., or any of the initializations at the start of the algorithm.

I think the time complexity is $n!$, as the number of cities is $n$, the for-loop in the algorithm above check for all the possible permutations of the distances between the cities. Did I understand the algorithm correctly? Any help or hints would be greatly appreciated.

• How long does it take to find the length of the tour? It's not $O(1)$. – Thomas Andrews May 28 '13 at 17:17
• I'd say $n \cdot n!$, since, for each tour you must add $n$ distances. – Jean-Claude Arbaut May 28 '13 at 17:17
• It depends on what is meant by "all possible tours". Up to rotation and reversal there are only $(n-1)!/2$ distinct tours. – Erick Wong May 28 '13 at 17:20
• @ErickWong, can you explain more about "up to rotation and reversal" and how did you get the number of distinct tours? – user59036 May 28 '13 at 17:35
• @user59036 For instance, when $n=3$ there is really only one tour (all tours have the same length as they are just going around the same triangle). This is assuming the distance matrix is symmetric. – Erick Wong May 28 '13 at 17:38