3
$\begingroup$

Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$.

It looks like I need to find a very small growing function $g$ that will satisfy $$\lim_{n\to{\infty}} \frac{1}{g} = 0 $$ and also $$\lim_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{g}}} = 0 $$

My first attempt was $g(n) = \log n$ but according to wolfram alpha, the second limit was not satisfied, I then tried $g(n) = \log\log n$ which according to wolfram does the trick.

But I'm not sure how to prove that $$\lim_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{\log\log n}}} = 0 $$

Im looking for a way to prove this, or find a simpler solution than $f=n^{1/\log\log n}$.

$\endgroup$
4
$\begingroup$

Take the log of your ratio to get $$ c\log\log n - \frac{\log n}{\log\log n} = \frac{c\log^2 m - m}{\log m}, \quad \text{where } m = \log n. $$ It is not hard to show that this tends to $-\infty$ as $m\to\infty$, and so as $n\to\infty$, which means that your ratio tends to zero as $n\to\infty$.

Indeed, since $c\log^2 m = o(m)$, for large enough $m$ we have $c \log^2 m - m \leq -m/2$. Since $2\log m = o(m)$, it follows that $\frac{m}{2\log m} \to \infty$ and so $\frac{-m}{2\log m} \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.