# Time complexity of the travelling salesman problem?

The dynamic programming approach breaks the problem into $2^n n$ subproblems. Each subproblem takes $n$ time resulting in a time complexity of $\mathcal{O} (2^n n^2)$.

• How are there $2^n n$ subproblems?

• Why does each subproblem take $n$ time?

$n$ refers to the number of cities needed to be travelled too.

Please refer to the following pseudocode for reference: http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/dynamic2.pdf

-
When asking a question about something you have quoted from a book/article/website, you have to indicate what it is you are quoting from! Otherwise, we have no idea what the quote is talking about. In this case, no one can answer the question without knowing what the dynamic programming algorithm actually is. –  Rahul Sep 3 '12 at 3:31
@RahulNarain Sorry! I just assumed that the dynamic programming approach is so common that anyone attempting to answer this question would be familiar with it. I'll add in a link anyway. –  user26649 Sep 3 '12 at 3:33
better luck at : cs.stackexchange.com –  Arjang Sep 3 '12 at 3:34
The title doesn't match the body. The body is not about the time complexity of the TSP but about that of a particular algorithm for solving it. –  joriki Sep 3 '12 at 3:46
This algorithm (I believe) is called Held-Karp and there are 2(ish) questions on cs.stackexchange.com discussing it. –  Kirk Boyer Sep 3 '12 at 3:48
show 1 more comment

There's a typo in the code: The loop should be over all subsets of size $s$, not $n$. The complexity is then immediate from the code and the paragraph underneath it: The two outer loops loop over the $2^{n-1}$ subsets containing $1$, and the inner loop and the $\min$ each loop over $O(n)$ cities (namely about $n/2$ on average).
As joriki points out there is a typo in the code: the loop should be over all subsets of size $s$ and not $n$. Looking at the initialization and the bounds for the loop we see that the total number of subproblems is $$\sum_{j=1}^{n-1} j {n-1 \choose j} = (n-1)2^{n-2} = O(n2^n)$$ Each subproblem $C(S,j)$ is computing the minimum of $s-1$ numbers (each number is computed in constant time). This is clearly $O(n)$ work per subproblem.
I don't follow you on how each subproblem is $O(n)$ time. Could you please expand on that? –  user26649 Sep 3 '12 at 6:22
Computing each of the $s-1$ numbers $C(S-\{j\},i)+d_{ij}$ takes constant time per number. Finding the minimum of these $s-1$ numbers involves $s-2$ comparisons (simply scan the list of values while keeping track of the smallest number found). Since $s \leq n$ this require $O(n)$ time. –  shoda Sep 3 '12 at 6:28