1
$\begingroup$

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

  • 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.2012-09-03
  • 0
    @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.2012-09-03
  • 0
    better luck at : http://cs.stackexchange.com/2012-09-03
  • 0
    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.2012-09-03
  • 0
    This algorithm (I believe) is called Held-Karp and there are 2(ish) questions on cs.stackexchange.com discussing it.2012-09-03
  • 0
    @FarhadYusufali: "Dynamic programming" is not an algorithm, it is a vague idea that can be used for developing algorithms in general. Are you claiming claim that there is exactly one possible way to apply this general idea to the specific Traveling Salesman Problem? If you understand the idea and the problem well enough to be sure of that, why do you need to ask anything about it?2012-09-03

2 Answers 2