Big-O notation for a function $f(x)$ that tends $\infty$ as $x \rightarrow \infty$ at an arbitrarily small rate?

Question

Is there are a big-O notation for a function $f(x)$ that tends $\infty$ at an arbitrarily small rate?

Obviously, the expression $\mathcal{O(1)}<f(x)<\mathcal{O}(\sqrt{\log(x)})$ is not good enough (I just randomly choose $\sqrt{\log(x)}$. What is a smart expression that I can replace $\sqrt{\log(x)}$ with?

Answer 1

You want to use the notation $f(x)=\omega(1)$.

The notation $f = \omega(g)$, $f$ dominate $g$, is defined as $$\forall k > 0 \, \exists n_0 \, \forall n > n_0 \colon |f(n)| > k\cdot g(n)$$ or $$\lim_{n \to \infty} \frac{\left|f(n)\right|}{g(n)} = \infty$$

Answer 2

There isn't a good way to do this with big-$O$ notation. No matter what expression you put into it, you can take a logarithm or a square root to find a significantly smaller function that still goes to infinity.

But there are other (albeit less common) notations for similar notions. In your case, you want $$f(x)\in \omega(1)$$This says that $f$ dominates $1$. Which is to say, for any multiple of $1$, $f$ is eventually bigger.