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?
Asked
Active
Viewed 390 times
1
hungry91
- 13
-
Do you know the definition of $O$ and $o$? – John Oct 23 '14 at 18:43
1 Answers
0
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)})$.
Eric M. Schmidt
- 3,717
-
Thanks, last sentence is particulary hepful. I think its possible to call this class "subpolynomial". In the third line there should be n instead of x obviously. – hungry91 Oct 23 '14 at 19:27
-
@user1416132 I have added a perhaps subtle caveat and explanation to my answer. – Eric M. Schmidt Oct 23 '14 at 19:42