Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

2 Answers

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).

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.