NP problems can be solved in deterministically EXPONENTIAL time?

Question

any problem in NP can be solved in deterministically exponential time, or we can say that any language in NP can be decided by an algorithm running in time 2^O(n^k) i.e., NP ⊆ EXP

informally speaking, we just try each one of the possible solutions and then decide it

However, there is a simple example that I can not figure out what's wrong with the idea i made

Here it is..

The Traveling Salesman problem : given a undirected graph G=(V,E) V=|n|

This is a well-known NP-complete problem, therefore, indeed belongs to NP

And I try to analyse the running time..like this:

I simply list out all the possible solutions, and there are (n-1)! possible tours in total

Then I check each one of them, it takes O(n) for each possible tour

The total running time will be O(n!)

It doesn't look like can be bounded above by 2^O(n^k), i.e., exponential time

where is the pitfall of this analysis?

or in the other word, how can we explain traveling salesman problem indeed can be decided by an algorithm running in time 2^O(n^k)

Answer 1

Note that

n! ≤ nⁿ = (2^{log n})ⁿ = 2^{n log n} ≤ 2ⁿ²

So n! = 2^O(n2), so n! ∈ EXP.

Hope this helps!