12
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

15
$\begingroup$

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

$\endgroup$
10
  • 3
    $\begingroup$ 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). $\endgroup$
    – frafl
    Feb 5, 2013 at 17:03
  • $\begingroup$ What if the number of terms is uncountable? :) $\endgroup$
    – SamM
    Feb 5, 2013 at 19:47
  • $\begingroup$ Using some well-ordering or do you want to replace the series by something more continuous? :) $\endgroup$
    – frafl
    Feb 5, 2013 at 20:13
  • $\begingroup$ @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. $\endgroup$
    – mrk
    Feb 6, 2013 at 10:34
  • 1
    $\begingroup$ @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. $\endgroup$
    – frafl
    Feb 9, 2013 at 15:03
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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?) $\endgroup$
    – user742
    Feb 5, 2013 at 23:48
  • 4
    $\begingroup$ @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”? $\endgroup$ Feb 6, 2013 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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