$g(f(n))\in o(g(n)/n)$ for any $f(n)\in o(n)$

25 Views Asked by At

Let $f:\mathbb{N}\rightarrow\mathbb{R}$ be a function such that $f(n)\in o(n)$. Is it always possible to find a function $g:\mathbb{N}\rightarrow\mathbb{R}$ such that $g(f(n))\in o(g(n)/n)$?

I'm pretty sure that if we pick $g$ to be "large enough", we can do this. But I don't know how to formalize the argument.

(See the definition of $o$ here.)

1

There are 1 best solutions below

0
On BEST ANSWER

$f(n)\in o(n)$, hence $f(n)\leq n/h(n)$ for some function $h(n)\to +\infty$. Thus $h(n)\geq 2$ for any large $n$. Take $g(n)=e^n$: $g(f(n))\leq e^{n/2}\in o(e^n/n)$.