Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
"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})$.
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.
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$.
