Little oh notation in the exponent

164 Views Asked by At

So I saw this notation in my analytic number theory course: $|f(n)|\leq n^{o(1)}$. So I am wondering whether this is the same as the notation $|f(n)|\leq o(n)$?

1

There are 1 best solutions below

4
On

$o(1)$ represents an unknown function that is tending to $0$ as $n\to\infty$; so, for every $\varepsilon>0$, we have $|o(1)|<\varepsilon$ when $n$ is large enough in terms of $\varepsilon$. Therefore $|f(n)| \le n^\varepsilon$ when $n$ is large enough in terms of $\varepsilon$, which is actually much stronger than $f(n) = o(n)$.

One example of a function satisfying $|f(n)| \le n^{o(1)}$ is $f(n) = \log n$.