Landau Big O, Little o notation, complex example

Question

I stumbled upon a set cardinality asymptotics:

$$O(n^{o(1)}),$$

I have a problem interpreting it.
Can somebody give me a hint how to look at it?

Answer 1

Suppose you have a function $f : \mathbb{N} \to \mathbb{R^+}$. To say that $f(n) = O(n^{o(1)})$ as $n \to \infty$ means that there exists a nonnegative function $g$ such that $g(n) = o(1)$ (that is, $\lim_{n\to\infty} g(n) = 0$) and constants $N, C > 0$, such that $f(n) \le Cn^{g(n)}$ for all $n > N$.

In particular, we can say that $f(n) = O(n^c)$ for all constants $c > 0$. Note that this last statement is weaker than you might think, because for each $c$, the value $C$ such that $f(n) < Cn^c$ can be different. We could rectify this by saying that $f(n) = O(n^c)$ uniformly in $c$, which means that the hidden constant in the Big O notation is the same no matter what $c$ is. When we add the "uniformly in $c$" phrase, we get a statement equivalent to the original statement $f(n) = O(n^{o(1)})$.