# Time complexity of Tsp using DP

this is the recursion formula for problem :

C(i,S) = min { d(i,j) + C(j,S-{j}) }


In fact, when I tried to implement it as a code, the following code came to my mind:

int TSP(i, S){
if(S.size == 0)
return dist(start_vertex,i)
min = inf
cost = inf
for(int j=0;j<S.size;j++)
{
cost = dist(i,S[j])+TSP(j,S-{j});
if(cost < min)
min = cost;
}
global_cost+=min;
return min;
}


Because this for compares n times to find the minimum, it means its recursion as:

T(n) = nT(n-1)+n ==> T(n) = O(n!)


Because each step we compare to find the minimum size of size S is, of course, the code is factorial. So what does it have to do with the subset and So why the complexity of time in the form of (n^2*2^n)? And what is the proof of its time complexity?

• Next time I suggest taking a look at Wikipedia. – Yuval Filmus Dec 12 '20 at 12:57

Your algorithm is known as the Held–Karp algorithm, and is described on Wikipedia, and also mentioned on the Wikipedia page on the traveling salesman problem.

Your implementation of the algorithm is wasteful. Using memoization, there are only at most $$n2^n$$ inputs. Since TSP runs in time $$O(n)$$ ignoring recursive calls, when using memoization, the total running time will be $$O(n^22^n)$$.

• doesn't this implementation exactly correspond to the dp algorithm? So why is it factorial? – Satar Dec 12 '20 at 13:55
• Right, thanks. Your implementation doesn't use dynamic programming. – Yuval Filmus Dec 12 '20 at 14:05