# Complexity of Held–Karp algorithm for TSP

The computing procedure:

$C(\{1\},\ 1) = 0$

for $s = 2$ to $n$ :

for all subsets $S\subseteq \{1,2,...,n\}$ of size  $s$ and containing $1$ :

$C(S, 1) = \infty$

for all $j\in S$ , $j \neq 1$ :

$C(S,j) = min\{C(S-\{j\},i) + d_{ij} : i\in S, i\neq j)\}$

return $min_{j,\ j\neq 1} C(\{1,2,...,n\}, j) + d_{j1}$

Complexity:

$\sum_{s=2}^{n}\binom{n-1}{s-1} \cdot (s-1) \cdot (s-1) + (n-1)$ , where for a specific $s$ ,

$\binom{n-1}{s-1}$ is the number of possible subset $S$ ;

the first $(s-1)$ represents the number of possible $j$ to consider;

the second $(s-1)$ means for each $j$ , to get the $C(S,j)$ , we have to consider $s-1$ possible $i$ .

$(n-1)$ is for the last returning statement.

By transformation:

$\sum_{s=2}^{n}\binom{n-1}{s-1} \cdot (s-1) \cdot (s-1)$

$=\sum_{2}^{n}\frac{(n-1)!}{(n-s)!(s-2)!} \cdot (s-1)$

$=\sum_{2}^{n}[\frac{(n-1)!}{(n-s)!(s-3)!} + \frac{(n-1)!}{(n-s)!(s-2)!} ]$

$=\sum_{2}^{n}[(n-1)(n-2)\binom{n-3}{s-3} + (n-1)\binom{n-2}{s-2}]$

The complexity is $O(n^2 2^n)$ . Note that $(n-1)!\approx \sqrt{2\pi (n-1)} (\frac{n-1}{e})^{n-1}$ . It is much larger than  $O(n^2 2^n)$ .

Refer to: