Analysis of time complexity of travelling salesman problem Recursive definition for travelling salesman problem can be written like this :-

T(i,S)=min((i,j)+T(j,S-{j})) for all j belonging to S, when S is not equal to NULL

T(i,S)=(i,S) when S is equal to NULL

Here, T(i,S) denotes the tour starting from i covering all vertices in Subset S and then travel back to i. 

I built the recursive tree and calculated the subproblems at each level. For k elements, number of subproblems comes out to be :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+(n-1)(n-2)(n-3)......(n-k).


For k=4, number of subproblems at level 1,2 and 3 are 3,6 and 6 respectively.

I tried to solve it but couldn't find the actual solution but it can be seen clearly that the time complexity is factorial. Now, in the recursion tree there are repeated function calls at the last level which we use to improve our time complexity using dynamic programming. Now, half of the function calls at last level are repeated that would reduce the number of subproblems to :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+((n-1)(n-2)(n-3)......(n-k))/2.

But, I think the time complexity is still factorial. I read on various resources that time complexity of travelling salesman problem using dynamic programming is $O(n^2*2^n)$ which is exponential.

Is there something wrong in my analysis? Can anyone prove how the time complexity comes out to be $O(n^2*2^n)$ ?
When solving TSP using dynamic programming you get something akin to the following:

TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length &lt; min {
      min = tour_length;
    }
  }
  return min;
}


(neighbors only returns target as a viable neighbor if no other choice is available)

This algorithm recursively finds the shortest tour starting from each neighbor and returns the minimum of those. If you do all this with dynamic programming you can calculate the amount of work you're doing like so:
There are $n$ possible start vertices and $2^n$ possible subgraphs. So this function will be called on at most $n\cdot2^n$ distinct arguments (the target never changes). Each call performs at most $O(n)$ work (there are at most $n$ neighbors). Hence the total work you're doing is $O(n^2\,2^n)$.