Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

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$ 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$ 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$ 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$ 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$ Commented Aug 13, 2017 at 14:35