Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 15 down vote accepted

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$.

share|improve this answer
3  
There are two series: one of functions (which may converge or not) and one of sets (where each set is a super set of the preceding one; this is why this series converges-see definition of lim inf and lim sup for sets). The first part answers the question without the $f_\infty$ part, the second part answers the $f_\infty$ part negatively (if $f_\infty$ is some sort of limes). –  frafl Feb 5 '13 at 17:03
    
What if the number of terms is uncountable? :) –  SamM Feb 5 '13 at 19:47
    
Using some well-ordering or do you want to replace the series by something more continuous? :) –  frafl Feb 5 '13 at 20:13
    
@Kaveh Thanks a lot, it makes a lot of sense now. If you could justify the use of limits and what that lim inf thing means, then that will complete my understanding. –  saadtaame Feb 6 '13 at 10:34
1  
@saadtaame: Maybe that's because the question above still does not ask what you want to know? If i remember correctly, you added the $f_\infty$ because of a comment suggested it. If you provide some context, maybe someone could rephrase the question again. –  frafl Feb 9 '13 at 15:03

Yes, it's possible to have an infinite chain.

I'm sure you're already familiar with some examples: $$ O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots $$ You have an infinite chain here: polynomials of growing degree. Can you go further? Sure! An exponential grows faster (asymptotically speaking) than any polynomial. $$ O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots O(e^x) $$ And of course you can keep going: $O(\mathrm{e}^x) \subseteq O(x\,\mathrm{e}^x) \subseteq O(\mathrm{e}^{2x}) \subseteq O(\mathrm{e}^{\mathrm{e}^x}) \subseteq \ldots$

You can build an infinite chain in the other direction too. If $f = O(g)$ then $\dfrac{1}{g} = O\left(\dfrac{1}{f}\right)$ (sticking to positive functions, since around here we discuss asymptotics of complexity functions). So we have for example:

$$ O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O\left(\dfrac{e^x}{x^2}\right) \subseteq O\left(\dfrac{e^x}{x}\right) \subseteq O(e^x) $$

In fact, given any chain of functions $f_1, \ldots, f_n$, you can build a function $f_\infty$ that grows faster than all of them. (I assume the $f_i$'s are functions from $\mathbb{N}$ to $\mathbb{R}_+$.) First, start with the idea $f_\infty(x) = \max \{f_n(x) \mid n \in\mathbb{N}\}$. That may not work because the set $\{f_n(x) \mid n \in\mathbb{N}\}$ can be unbounded. But since we're only intersted in asymptotic growth, it's enough to start small and grow progressively. Take the maximum over a finite number of functions. $$ f_\infty(x) = \max \{f_n(x) \mid 1 \le n \le N \} \qquad \text{if \(N \le x \lt N+1\)} $$ Then for any $N$, $f_N \in O(f_\infty)$, since $\forall x \ge N, f_\infty(x) \ge f_N(x)$. If you want a function that grows strictly faster ($f_\infty = o(f_\infty')$), take $f_\infty'(x) = x \cdot (1 + f_\infty(x))$.

share|improve this answer
    
All of this answers (your and other one), is based on assuming that we know what happens in infinity, they are not satisfiable for me, I don't know about the OP (why we shouldn't have closed group with infinite size?) –  user742 Feb 5 '13 at 23:48
4  
@SaeedAmiri I'm sorry, I don't understand your comment: what do you mean by “we know what happens in infinity, they are not satisfiable for me”? –  Gilles Feb 6 '13 at 0:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.