[Solved]: Infinite chain of big $O’s$

We first need to clarify what we mean by “does this hold if we have an infinite chain?”. We interpret it as an infinite sequence of functions ${f_i:mathbb{N}tomathbb{N} mid 1leq i}$ such that for all $i$ we have $f_i(n) = O(f_{i+1}(n))$. Such a sequence might not have a last function. We can look at the limit of the functions in the sequence, i.e. $f_infty(n) = lim_{ito infty} f_i(n)$. However it is possible that the limit does not exists. And even in the case that it exists we might not have $f_1(n) = O(f_infty(n))$. For example consider the sequence of functions $f_i(n) = frac{n}{i}$. For each $i$, $f_i(n)=Theta(n)$ and therefore $f_i(n) = O(f_{i+1}(n))$. However $f_infty(n)=lim_{itoinfty}f_i(n)=0=Theta(1)$ thus $f_1(n) neq O(f_infty(n))$. On the other hand we can look at the limit of the sequence of the classes which doesn’t need to be equal to the class of the limit of the functions. We have $f_i in mathcal O(f_{i+1})$, therefore $mathcal O(f_i) subseteq mathcal O(f_{i+1})$ and $f_j in lim_{irightarrowinfty} mathcal O(f_i) = limsup_{irightarrowinfty} mathcal O(f_i) = liminf_{irightarrowinfty} mathcal O(f_i) = bigcup_{n in mathbb{N}}bigcap_{k>n}mathcal O(f_k)$ for all $j$. The limit superior contains all elements (functions in this case) which occur infinitely often and the limit inferior contains all elements which occur in all $mathcal O(f_i), i ge n_0$ for some $n_0$ (which may depend on the element). Since the sequence of classes is monotonically increasing both exist and they are equal. This justifies the usage of $lim$.