# Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as “good” and practical as any other polynomial algorithm?

If the complexity of an arbitrary algorithm to solve any NP problem after analysis is $\Theta(2^\sqrt{n})$ then is this algorithm considered as "good" and practical algorithm?

I know that in algorithm analysis and computational complexity theory every algorithm with any polynomial complexity is considered as "good" and practical algorithm, although in mathematics and calculus $2^\sqrt{n}$ isn't polynomial by definition, but so $n\log n$, but $\Theta(n\log n)$ counts as "good" and practical algorithm to solve any NP problem.

I have already graphed the functions: $x, x\log_2x, x^2, 2^\sqrt{x}$ and $x^3$ by using some online function plotter, and for some large $x$, it appears that $x^3>2^\sqrt{x}>x^2>x\log_2x>x$

So I think that $\Theta(2^\sqrt{n})$ is practical and "good" as $\Theta(n\log n)$ is, although both of them are not polynomial by definition.

Am I right?

• Any algorithm which works in practice is practical. An algorithm whose running time is $\Theta(2^{\sqrt{n}})$ will probably be practical only for small $n$ (say in the order of thousands), though it depends on the hidden constants in the asymptotic notation. – Yuval Filmus Aug 12 '17 at 20:04
• An algorithm running in time $\Theta(n\log n)$ runs in polynomial time. An algorithm runs in polynomial time if it runs in time $O(n^C)$ for some $C$. In this case, we can take any $C>1$. – Yuval Filmus Aug 12 '17 at 20:05
• Are you sure that there is no mistake? $x^3$ is greater than $2^{\sqrt x}$ for some numbers, but it is still exponential, and from some point on it will dominate. Take for example $x = 1024, x^3 = 1 073 741 824, 2^{\sqrt x} = 4 294 967 296$, and from that point on it is always greater. – Evil Aug 12 '17 at 20:09
• This isn't really a question in complexity theory – complexity theory is not about practical computation. The definitions that are used in complexity theory are imperfect model of the practical notion of efficiency. – Yuval Filmus Aug 12 '17 at 20:27
• @Evil, well, I was not correct, since ETH is a conjecture that SAT can't be solved in time $o(2^n)$, but exponential function is any function of type $2^{poly(n)}$. – rus9384 Aug 13 '17 at 14:35

Complexity is how an algorithm increases its number of steps in comparison to $n$ when we scale $n$ to a large value.
For very small $n$ , an algorithm with complexity $\Theta(2^\sqrt{n})$ can behave nearly as good as an algorithm running in polynomial time.But if we increase the $n$ , then certainly the algorithm with polynomial time will give much faster results.That's how algorithms are compared.One important thing to remember is that your $n$ is a variable related to input size and if this occurs as a power of something in time complexity then you can be sure that the algorithm is going to take a lot of time for large values of $n$.
$\Theta(2^\sqrt{n})$ is not as good as $\Theta(n\log n)$