Travelling Salesman: Big O Complexity when starting city is fixed We are studying the Travelling Salesman problem in my high school class, and I am wondering what the Big O complexity of the TSP is when you MUST start and end at the same city. For example, given 4 cities labelled A,B,C,D and you MUST start and end at A, what is the big O notation for this? Is ((n-1)!)/2 for both symmetrical and asymmetric cases?

Thanks
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!)$.