0
$\begingroup$

Let $\varepsilon \in (0,1)$. I wish to show that $2^{\log^{1-\varepsilon}(n)}\in \omega(\operatorname{polylog}(n))$. I attempted to turn this into a function and use L'Hospital's rule but that got me nowhere even when taking $\log^1 n$ (I hope i did not make a mistake in the derivatives): $$ \lim\frac{\log x}{2^{\log^{1-\varepsilon}(x)}}=\lim\frac{1}{\ln 2 \cdot 2^{\log^{1-\varepsilon}(x)}\cdot(1-\varepsilon)\cdot\log^{-\varepsilon}(x)} $$

Polylog should be $\log^k(n)$ for some $k$. To generalize, I wanted to use induction on $k$ ($k$ being the exponent in the polylog), but the term $\log^{-\varepsilon}(x)$ in the denominator does not help.

An approach not turning it into a function but merely working with the sequence with $n\in \mathbb{N}$ would be even more appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

I assume that you would like to show (let me change the base) that $\exp{\log(x)^{1-\varepsilon}}$ grows faster than any power of $\log$. In other words, you wish to show that $e^{x^{1-\varepsilon}}$ grows faster than any power of $x$. This simply follows from the fact that $e^x \in\omega(x^k)$ for any $k\ge 0$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .