1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Vladislav Mar 16 at 17:13
  • $\begingroup$ $2^N$ for a single set $\endgroup$ – Padwas Mar 16 at 17:26
  • $\begingroup$ Ah so they dont actually store all permuations they just store all subsets which represent all tours ? That would be $2^N$ not N! $\endgroup$ – Padwas Mar 16 at 17:27
  • $\begingroup$ Yes. "...visiting each vertex in set S exactly once, starting at..." $\endgroup$ – Vladislav Mar 16 at 17:29
3
$\begingroup$

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

In fact, every problem in NP can be solved using polynomial space, using a brute force approach that simply goes over all possible witnesses, and for each of them, verifying (in polynomial time per witness) whether it is a valid witness. This extends the brute force algorithm for TSP.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.