find a function $f:\mathbb{N}\to \mathbb{N}$

Question

Find $f:\mathbb{N}\to\mathbb{N}$ s.t. $n^2 = o(f(n))$ and $f(n) = o(n^{2+\varepsilon})$.

So I thought about the function $f(n) = \left\lfloor n^{2+\varepsilon} \right\rfloor$

I already was able to prove that $f(n) = o(n^{2+\varepsilon})$, but had some troubles with the other part.

I tried to use the fact that $$\forall x. x-1 \le \lfloor x \rfloor$$

I'd be glad for help (by the way, is that a sufficiently elegant function for the problem?)

Answer 1

$f(n) = n^2\ln(n)$.

$\frac{n^2}{f(n)} =\frac1{\ln(n)} \to 0$ so $n^2 = o(f(n))$.

$\frac{f(n))}{n^{2+\epsilon}} =\frac{\ln(n)}{n^{\epsilon}} \to 0 $ since $\ln(n) = o(n^{\epsilon})$ for any $\epsilon > 0$ so $f(n) = o(n^{2+\epsilon}) $ for any $\epsilon > 0$.

Note: To show $\frac{\ln(n)}{n^{\epsilon}} \to 0$,

$\begin{array}\\ \frac{\ln(n)}{n^{\epsilon}} &=\frac1{\epsilon}\frac{\epsilon\ln(n)}{n^{\epsilon}}\\ &=\frac1{\epsilon}\frac{ln(n^{\epsilon})}{n^{\epsilon}}\\ &\to 0 \end{array} $

since $\frac{\ln(n)}{n} \to 0 $.

Answer 2

For $n>1$: Let $g(n)=1/\sqrt {\log n}$ .

Let $f(n)=$Floor$(n^{2+g(n)}).$

Then $f(n)n^{-2}\geq$ $(n^{2+g(n)}-1)n^{-2}=$ $n^{g(n)}-n^{-2}=$ $(e^{\log n})^{g(n)}-n^{-2}=$ $e^{\sqrt {\log n}}-n^{-2}$, which $\to \infty$ as $n\to \infty.$

And for any fixed $\epsilon >0$ we have $n^{2+\epsilon}f(n)^{-1}\geq$ $n^{2+\epsilon}n^{-2-g(n)}=$ $n^{\epsilon-1/\sqrt {\log n}}$, which $\to \infty$ as $n\to \infty.$

Remark: Floor$(n^{2+\epsilon})$ is NOT $o(n^{2+\epsilon})$ as $n\to \infty.$ when $\epsilon >0.$

Because $1\geq$ Floor$(n^{2+\epsilon})n^{-2-\epsilon}\geq 1-n^{-2-\epsilon},$ which $\to 1$ as $n\to \infty.$