2
$\begingroup$

I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.

The Traveling Salesman problem (TSP) is famous. Given a list of cities and the distances in between them, the task is to find the shortest possible ​tour​ that starts at a city, visits each city exactly once and returns to a starting city. A particular tour can be described as list of all cities [c1,c2, c3, ... ,cn] ordered by the position in which they are visited with the assumption that you return from the last city to the start.This is a hard problem, that is, there is no known efficient solution for this problem and we are not expecting one any time soon. Your task is to analyze the following brute force approach to solving the problem:

Consider the following algorithm for solving the TSP:

n = number of cities
m = n x 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

State the worst-case (big-O) complexity of this algorithm in terms of ​​(number of cities)?You may assume that matrix lookup is one step O(1). For deriving big-O here, you need not count the if-statement or the for-loop conditional (i.e., testing to see when the for-loop is done), or any of the initializations at the start of the algorithm.

So far I know that there are 2 statements that will be executed after the if statement and I think there n! permutations of tours. Am I correct so far. How would I figure out the amounts of steps for "find the length of tour"?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You've almost got it! Remember, you're going to visit each city exactly once in a tour. Which means you have to look up $n-1$ distances for each one. This is $O(n)$, since the problem specifies that matrix lookup is assumed to be $O(1)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So would the big O notation be O((n-1)!)? Or would it be O((n-1!) + O(1)? $\endgroup$
    – John
    Commented Apr 17, 2019 at 5:30
  • $\begingroup$ @John You can ignore lower-order terms, but you can't ignore lower-order factors. So it's $O(n!n)$: $O(n!)$ different paths to look at, $O(n)$ work for each path. $\endgroup$
    – Draconis
    Commented Apr 17, 2019 at 15:42
0
$\begingroup$

The tour is exactly $n$ elements list, where $n$ is number of cities. So it takes n - 1 additions and one check if it is smaller than already seen.

You are right that there are $n!$ permutations, but last city is fixed, so $(n-1)!$ tours. If problem is symmetric you can divide number of permutations by 2. It changes nothing in big-O notation.

You have to get these permutations, but it is also negligible. This yields $\mathcal O(n! * n)$ worst case runtime. In fact, $\mathcal O(\frac{(n-1)!}{2} * (n - 1))$ is of exactly same order as previous one.

If you add 'if' statements, you will get something like 3(n-1) which is still simply $\mathcal O(n)$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I'm still a little bit confused. The total number of permutations is (n-1)! so would the big O notation be O((n-1)!) because we can ignore the lower order terms? $\endgroup$
    – John
    Commented Apr 17, 2019 at 5:37
  • $\begingroup$ No, we can ignore constant factors (like 3, -1), but you $n!$ times run something linear (3n or so), so you cannot ignore this factor. $\mathcal O(n! * n)$ is not the same as $\mathcal O(n!)$. $n$ here is variable, not constant, In soft big-O ( Õ ) you can ignore logarithmic factors, but still not linear or bigger. You can check whether $n*n! \in \mathcal O(n!)$ to be sure. $\endgroup$
    – Evil
    Commented Apr 17, 2019 at 5:43
  • $\begingroup$ Okay. If there are (n-1)! total tours because the last city is fixed, then how did you get O(n!*n) and not O((n-1)!)? $\endgroup$
    – John
    Commented Apr 17, 2019 at 5:52
  • $\begingroup$ Because it does not matter whether it is n! or (n-1)! in asymptotic case. n! times you check the length n, this minimal tour distance is accounted for. (n-1)! * n, where (n-1)! is number of possible tours and n is number of cities to add distances. O(1) in your excersise means that looking up value is constant time, so we count it as 1. I honestly think, that you should convince yourself that c*n = $\mathcal O(n)$ and then look at current problem once again. $\endgroup$
    – Evil
    Commented Apr 17, 2019 at 5:57
  • $\begingroup$ I see. Thank you. Last question, why did you multiply (n-1)! by n and not add (n-1)! and n? $\endgroup$
    – John
    Commented Apr 17, 2019 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.