How much do I have to reduce the factorial in Order to reach Polynomial Complexity?

Question

First of all is my first question so sorry if it will not be much clear.

Suppose that I have to find the minimal path (Travelling Saleseman Problem) in graph where I visit All the city and I return to the starting one. The brute force algorithm has a Factorial Complexity. So suppose that I have 50 cities to visit my algorithm will run in 50!

How much do I have to reduce that complexity always considering a factorial algorithm in order to reach a polynomial complexity? For example if my algorithm run in 20! instead then 50! and I find the optimal solution is it polynomial?

Sorry if the question is not much clear.

Answer 1

Both $50!$ and $20!$ are constants. In that 50-city example, the number of cities is always the same so the complexity will always be constant.

When people speak of polynomial/exponential/factorial time, they're not talking about the running time when the number of cities is fixed (50 in your example). Instead, they're talking about the time as a function of the size of the instance. So, to solve TSP in time that is polynomial in the number of cities, you need to find an algorithm $A$, such that the running time of $A$ when given $n$ cities is $O(P(n))$ for some polynomial $P$. See here for a formal definition of big $O$-notation.

Answer 2

Let $T(n)$ denote the number of steps your algorithm takes for a graph on $n$ vertices. If there exists a constant $k \geq 0$ such that:

$$\lim_{n \to \infty} \left|\frac{T(n)}{n^{k}} \right| < \infty,$$

then the algorithm runs in polynomial time.

Note that this criterion deals with sufficiently large $n$, rather than $n = 50$ or $n = 20$. Asymptotic behavior captures what happens for sufficiently large inputs, rather than your favorite test case(s).