0
$\begingroup$

I was told that exponential time always beats polynomial time but doesn't this not work for:

$n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$?

If we take $log_2$ on both of them we get:

$\frac{1}{2}log \,n > \sqrt{log \,n}$

which seems that what I was told is incorrect.

  • Did I not hear the caveats?
  • Have I mislabelled exponential and polynomial functions?
  • If this view is wrong. What's greater $n^{\frac{1}{2}}$ or $2^{\sqrt{log \,n}}$? How would you show it?
$\endgroup$
1
  • $\begingroup$ $2^{\sqrt{\log n}}$ does not grow exponentially! In fact it grows slower than any root of $n$ (and faster than any polylogarithm). $\endgroup$
    – Steven
    Feb 15 at 18:40
2
$\begingroup$

"exponential time always beats polynomial" we understand as for $a>1$ and any $k\in \mathbb{R}$ we have $n^k \in O(a^n), n\to \infty$.

But if you consider substitution of $n$ with some arbitrary function, then, of course, generally, $n^{f(n)} \in O(a^{g(n)})$ will be wrong. We can even reverse functions with appropriate substitution: $n^{f(n)}=n^{\log_na^n} = a^n $ and $a^{g(n)} = a^{\log_a n^k} = n^k$.

Your example $\sqrt{n}$ vs $2^{\sqrt{\log_2 n}}$ is not polynomial vs exponential, but polynomial vs some elementary function.

Addition. Now let's compare $\sqrt{n}=2^{\log_2 \sqrt{n}}$ and $2^{\sqrt{\log_2 n}}$. As exponential with base $2$ is strictly increasing, then it is equivalence to compare $\log_2 \sqrt{n}$ and $\sqrt{\log_2 n}$. Considering function $f(x)=\log_2 \sqrt{x} - \sqrt{\log_2 x}$, for $x>1$, we have $$f'(x)=\frac{1}{2x\ln 2}-\frac{1}{2x\ln 2\sqrt{\log_2 x}} = \frac{\sqrt{\log_2 x}-1}{2x\ln 2\sqrt{\log_2 x}}$$ So $f$ is decreasing on $(1,2)$ and increasing on $(2,+\infty)$. As it easy to see, that $f(1)=f(16)=0$, then we can conclude that on $(1,16)$ function is negative and on $(16,+\infty)$ function $f$ is positive, so $$\sqrt{n}=2^{\log_2 \sqrt{n}} \gt 2^{\sqrt{\log_2 n}}$$ for $n \gt 16$. This gives $2^{\sqrt{\log_2 n}} \in O(\sqrt{n})$.

Additionally, if we consider $g(x)=\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}$, then $$\lim\limits_{x \to +\infty}\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}= \lim\limits_{x \to +\infty}\sqrt{\log_2 x}=+\infty$$ which gives $2^{\sqrt{\log_2 n}} \in o(\sqrt{n})$.

$\endgroup$
2
  • $\begingroup$ Added an edit to the question: And what's greater $n^{\frac{1}{2}}$ or $2^{\sqrt{log \,n}}$? $\endgroup$ Feb 15 at 17:34
  • $\begingroup$ Wrote addition. $\endgroup$
    – zkutch
    Feb 15 at 21:25
1
$\begingroup$

What does it mean "beat"? From the context, I'm deriving that in computational complexity it is said that a polynomial time is always better than an exponential time.

Now, if you look here a polynomial time is defined as $O(n^c)$, while an exponential time is defined as $O(c^n)$, where $c$ is a positive constant, and $n$ increases without bound.

Your example does not involve really an exponential and a polynomial. It is a polynomial and "something else". Since the $\log$ balances the exponential. Therefore it is not an exponential.

In order to see which function grows larger, you can even draw them. Just for the sake of the argument let's consider the inputs: 1, 10, 100 for $n$.

Case $n = 1$

Then you have that $n^\frac{1}{2}$ is $1$, while $2^\sqrt{\log n}$ is $1$.

Case $n = 10$

Then you have that $n^\frac{1}{2}$ is $3.16$, while $2^\sqrt{\log n}$ is $3.53$.

Case $n = 100$

Then you have that $n^\frac{1}{2}$ is $7.8$, while $2^\sqrt{\log n}$ is ~$6$.

So $n^\frac{1}{2}$ grows significantly faster. That is mainly due to the logarithm over the $2$.

So to reply to the question: which one of the two function is greater? It is up to which $n$. The first function grows faster, but for small values of $n$, the second function is bigger. The more $n$ grows, the more the first function will grow, therefore being greater than the second one.

$\endgroup$
3
  • $\begingroup$ Added an edit to the question: And what's greater $n^{\frac{1}{2}}$ or $2^{\sqrt{log \,n}}$? $\endgroup$ Feb 15 at 17:33
  • $\begingroup$ I edited my answer to reply to the question $\endgroup$ Feb 15 at 17:55
  • $\begingroup$ Be careful $O(c^n)$, also includes all polynomials (and slower). A similar comment applies to $O(n^c)$. You probably want to use $\Theta(\cdot)$. $\endgroup$
    – Steven
    Feb 15 at 18:59
1
$\begingroup$

You will easily see that the $\sqrt n$ function dominates (or "beats", in your words) the $2^{\sqrt \log n}$ function when $n \to \infty$ if you make the following substitution: $$n = 2^{k^2}$$ Then: $$\sqrt n=2^{\frac{k^2}{2}}$$ $$2^{\sqrt \log n}=2^k$$ So, the first one is larger than the second one when $k \to \infty$.

$\endgroup$

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.