Time complexity of Tsp using DP

Question

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?

Answer 1

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