2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 12 '17 at 20:04
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Aug 12 '17 at 20:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Evil Aug 12 '17 at 20:09
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 12 '17 at 20:27
  • 2
    $\begingroup$ @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)}$. $\endgroup$ – rus9384 Aug 13 '17 at 14:35
2
$\begingroup$

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)$

$\endgroup$
  • 1
    $\begingroup$ I understood your answer. Thank you. That's what I wanted to know. $\endgroup$ – Farewell Stack Exchange Aug 12 '17 at 21:26
  • 1
    $\begingroup$ I am glad it helped :) $\endgroup$ – Romantic Electron Aug 12 '17 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.