# 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. Dec 12 '20 at 12:57

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