The Held–Karp algorithm has exponential time complexity \Theta(2^n n^2), significantly better than the superexponential performance \Theta(n!) of a brute-force algorithm. Held–Karp, however, requires \Theta(n 2^n) space to hold all computed values of the function g(S, e), while brute force needs only \Theta(n^2) space to store the graph itself.
