Travelling Salesman: Big O Complexity when starting city is fixed
The start city makes no difference. You're constructing a tour through all the cities, so it doesn't matter if you do ABCDEA or CDEABC.

Held&ndash;Karp solves TSP in time $O(n^22^n)$, which is much faster than $\Theta(n!)$.