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.

  • $\begingroup$ How long does it take to find the length of the tour? It's not $O(1)$. $\endgroup$ – Thomas Andrews May 28 '13 at 17:17
  • $\begingroup$ I'd say $n \cdot n!$, since, for each tour you must add $n$ distances. $\endgroup$ – Jean-Claude Arbaut May 28 '13 at 17:17
  • 1
    $\begingroup$ It depends on what is meant by "all possible tours". Up to rotation and reversal there are only $(n-1)!/2$ distinct tours. $\endgroup$ – Erick Wong May 28 '13 at 17:20
  • $\begingroup$ @ErickWong, can you explain more about "up to rotation and reversal" and how did you get the number of distinct tours? $\endgroup$ – user59036 May 28 '13 at 17:35
  • $\begingroup$ @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. $\endgroup$ – Erick Wong May 28 '13 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.