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?

Improve this question
$\endgroup$
11
  • 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
    Commented Aug 12, 2017 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
    Commented Aug 12, 2017 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
    Commented Aug 12, 2017 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
    Commented Aug 12, 2017 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
    Commented Aug 13, 2017 at 14:35

1 Answer 1

Reset to default
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)$

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

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