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

Problem Detail: 

First, let me write the definition of big $O$ just to make things explicit.

$f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ such that $0\le f(n)\le cg(n), \forall n\ge n_0$

Let's say we have a finite number of functions: $f_1,f_2,\dots f_n$ satisftying:

$O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n)$

By transitivity of $O$, we have that: $O(f_1)\subseteq O(f_n)$

Does this hold if we have an infinite chain of $O's$? In other words, is $O(f_1) \subseteq O(f_\infty)$?

I'm having trouble imagining what's going on.

Asked By : saadtaame

Answered By : frafl

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}\to\mathbb{N} \mid 1\leq 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_{i\to \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_{i\to\infty}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_{i\rightarrow\infty} \mathcal O(f_i) = \limsup_{i\rightarrow\infty} \mathcal O(f_i) = \liminf_{i\rightarrow\infty} \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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9506