Question about big $O$ notation

64 Views Asked by At

We all know that exponential functions grow faster than polynomials. Let us consider the following function: $f(n) = n^{a_1} \cdot (\log n)^{a_2}\cdot (\log \log n)^{a_3} \cdot (\log \log \log n)^{a_4}\cdots$ where the leading coefficient $a_k$ is positive.

I think anything that is "slowly growing" has this type of asymptotic expansion. In short, this type of representation is "complete": there is nothing between $n$ and $n \log n$ other than a member of the above class, for instance $n \cdot (\log n)^{1/2}\cdot(\log \log \log n)^5 / (\log \log n)^3$.

Is my statement true? How can one make it rigorous, assuming it is correct? Also,

(1) What would be the slowest growing function that grows faster than the fastest growing function in the above class?

(2) Provide an example of function growing faster than the fastest growing function in that class, but more slowly than $\exp n$.

(3) What happens if you allow the coefficients $a_k$ not to be bounded, and the sequence $\{a_k\}$ to be infinite? For instance consider $f(n) = n \cdot (\log n)^2 \cdot (\log \log n)^4 \cdot (\log \log \log n)^8\cdots$

In short, is there some kind of topological framework that handles manipulations over these functions? Indeed, they are not functions, but asymptotic representations or quantities instead. It's a different type of mathematical objects, with its own arithmetic and topology.