# Time complexity of travelling salesman problem

Time complexity of travelling salesman problem is $O(n^2*2^n)$ using held-karp algorithm. Now, if don't use dynamic programming and solve it using the recursive procedure, time complexity is still $O(n^2*2^n)$. I know there are overlapping of subproblems and there will be less computations but the time complexity is not getting better with the use of dynamic programming. Moreover, space complexity using held-karp is also $O(n*2^n)$ which is very large. We mostly use dynamic programming when we can improve the time complexity.

So, should we use dynamic programming here?

Here is the recursive approach..

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 < min {
min = tour_length;
}
}
return min;
}


Time complexity using the recursive method is trying all "reachable" permutations of nodes before getting back to the first node which is in worst case $$O(n!)$$ (if all permutations are reachable).