Example of functions satisfying certain little-oh condition

38 Views Asked by At

Let $f:\mathbb{Z}_{>0} \rightarrow \mathbb{C}$ be a function. Now require $f$ to satisfy the condition $$ |f(n)|\leq n^{o(1)} $$ where $o(1)$ is any function $g(n)$ satisfy $\frac{g(n)}{1}\rightarrow 0$ as $n\rightarrow\infty$.

Can someone give some example of such $f(n)$ besides constant functions?

2

There are 2 best solutions below

0
On

$f(n)=\log n, n \ge 2$ and $g(n)=(\log n)^{-1/2}=o(1), n \ge 2$; $n^{g(n)}=e^{(\log n)^{1/2}}$ and we have $(\log n)^{1/2} \ge \log \log n$ so $n^{g(n)} \ge e^{\log \log n}=\log n$

(if needed of course we can use a small constant and take $f(n)=C\log n$ to take care of small cases but I think the inequality $(\log n)^{1/2} \ge \log \log n$ holds for all $n \ge 2$ not only for large $n$ where it is trivial)

0
On

Other more interesting examples are the divisor function and $n/\phi(n)$ where $\phi$ is the Euler function. Not so interesting examples are constant functions.