# What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?

For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$?

It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $L\in\mathcal{O}(\lg(n))$ or $L\in\mathcal{O}(\mathrm{polylog}(n))$?

• Are you sure you don't mean $\forall \varepsilon > 1$? – Reinstate Monica Jun 28 '18 at 12:55
• @Solomonoff'sSecret no it is greater than zero. for example any language in O(lg n) has above conditions. but I want greater complexity (than logarithmic) class with above conditions if exists. – Mohsen Ghorbani Jun 28 '18 at 13:00
• Sometimes the notation $O(n^{o(1)})$ is used for this. – Yuval Filmus Jun 28 '18 at 14:20
• @YuvalFilmus Wouldn't that mean $\{f : \exists \varepsilon, f\in O(n^\varepsilon)\}$ while the class in the question is $\{f:\forall \varepsilon, f\in O(n^\varepsilon)\}$? – xavierm02 Jun 28 '18 at 14:41
• No, $f = O(n^{o(1)})$ if there exists $g = o(1)$ such that $f = O(n^g)$. If $f$ is a function satisfying your condition, let $g = \log_n f$. For all $\epsilon > 0$ there exists $C_\epsilon$ such that $f \leq C_\epsilon n^\epsilon$, and so $g \leq \log_n C_\epsilon + \epsilon$. In particular, for every $\epsilon > 0$ we can find $n$ large enough so that eventually $g < 2\epsilon$. Hence $g = o(1)$. – Yuval Filmus Jun 28 '18 at 14:45

Define $$A := \bigcap_{\varepsilon > 0} O(n^\varepsilon) = \bigcap_{i \in \mathbb{N}} O(n^\frac{1}{i}).$$ This complexity class is analogous to $$B := \bigcap_{i \in \mathbb{N}} \Omega(n^i),$$ the class of super-polynomial functions, in the sense that if $f$ is strictly increasing, $f \in A \Leftrightarrow f^{-1} \in B$. There isn't a "nice" description of $B$ so you wouldn't expect a "nice" description of $A$.
Note that $e^\sqrt[i]{n} \in B$ so $\log^i n \in A$.