# Space complexity of Travelling Salesman Problem

I am having trouble coming up with the space complexity of the TSP algorithm.

https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

To me the space complexity for the brute force is the cost of storing all possible permutations right ? That should take space O($$N!$$) where N is the number of cities/nodes/vertexes.

Similarly for the Dynamic Programming algorithm it stores all tours, that is also O($$N!$$), but the site says the space complexity is O($$2^{N}$$)

Can someone explain if my logic for space complexities is correct, especially for the Dynamic Programming algorithm.

Thank you

• They use memory for storing $C(S, i)$ where $S$ is a subset of vertexes set. How many subsets does a set of $N$ elements have? Mar 16, 2020 at 17:13
• $2^N$ for a single set Mar 16, 2020 at 17:26
• Ah so they dont actually store all permuations they just store all subsets which represent all tours ? That would be $2^N$ not N! Mar 16, 2020 at 17:27
• Yes. "...visiting each vertex in set S exactly once, starting at..." Mar 16, 2020 at 17:29

The brute force solution enumerates all permutations. You can easily encode each permutation using $$n\log n$$ bits, since you can encode it as a list of numbers from $$1$$ to $$n$$, and each number takes $$\log n$$ bits to encode. You can check that a given permutation corresponds to a tour using $$O(\log n)$$ additional bits of space, so in total the space requirements are $$O(n\log n)$$.
The dynamic programming solution, as mentioned in the comments, uses a table of size $$O^*(2^n)$$. This is much more memory than the brute force solution, but the complexity is exponential instead of factorial, which is much better.
(The notation $$O^*$$ means that we ignore polynomial factors.)