18
$\begingroup$

There are many asymptotic notations like the big O notation: big Omega notation, little o notation, ... Thus there are many arithmetic rules for them. For example Donald Knuth states in Concrete Mathemtics (p. 436) the following rules (without a proof):

  • $f(n)=O(f(n))$
  • $c O(f(n)) = O(f(n))$, if $c$ is constant
  • $O(O(f(n))) = O(f(n))$
  • ...

My Question: Can you recommend a reference where all arithmetic rules of the asymptotic notations are stated and proved? It would be great if also the connections between the asymptotic notations are formulated and shown, e.g. $O(o(f(n))=o(f(n))$.

My research results so far:

Reason for my question: I write my thesis which heavily bases on asymptotic notations. I want to prove all the arithmetic rules I used which are a lot... (I also use other notations like the big Delta notation). A list of already proved arithmetic rules - which I can cite - would be great here ;-)

Update: I had an idea to minimize the number of needed arithmetic rules via generalizing the concept of asymptotic notations. I describe this idea in the MO thread Generalization of asymptotic notations like big O or little o notation.

$\endgroup$
4
  • 2
    $\begingroup$ Very well asked question. If you don't get an answer in the next 2 days, let me know and I'll add a bounty. $\endgroup$ Nov 8, 2015 at 18:41
  • 1
    $\begingroup$ I use this notation all the time, and I've never committed such arithmetic rules to memory. I think it's easier to prove them when you need them. $\endgroup$
    – zhw.
    Nov 8, 2015 at 18:41
  • $\begingroup$ @Omnomnomnom: Oh, thanks a lot! ;-) $\endgroup$ Nov 8, 2015 at 18:58
  • $\begingroup$ @zhw: I added the motivation for my question... I would like to cite such a list to save time and to keep the thesis short ;-) $\endgroup$ Nov 8, 2015 at 18:59

4 Answers 4

13
+100
$\begingroup$

A beautiful presentation can be found in N.G. De Bruijn classic: Asymptotic Methods in Analysis. You will find arithmetic rules of the Bachmann-Landau symbols in the section Introduction.

Another classic is Asymptotics and Special Functions by F.W.J. Olver. The first chapter Introduction to Asymptotic Analysis also provides a thorough introduction of $\sim, \mathcal{o}$ and $\mathcal{O}$ notation.

For a historical discussion I recommend the paper Big Omicron and Big Omega and Big Theta by D.E. Knuth.

$\endgroup$
1
  • $\begingroup$ @tampis: Thanks a lot for accepting my answer and granting the bounty! Best regards, $\endgroup$ Nov 19, 2015 at 22:20
3
$\begingroup$

I had an idea how to shorten the list of arithmetic rules. Thanks to a comment by Douglas Zare the list of necessary arithmetic rules became even shorter.

The idea: Note, that $O(\cdot)$ is fully described by knowing $O(1)$ because $$(\epsilon_n)_{n\in\mathbb N} \in O(a_n) \iff \left(\left|\frac{\epsilon_n}{a_n}\right|\right)_{n\in \mathbb N} \in O(1)$$ This circumstance can be condensed in the relation $a_ n O(1) = O(a_n)$. The above equivalence and characteristic equation $a_n A(1) = A(a_n)$ hold for other asymptotic notations too, i.e for all $A\in\{o,\omega, \Theta, S\}$ (whereby $(\epsilon_n)_{n\in\mathbb N} \in S(a_n)$ shall be the notation for $\epsilon_n \sim a_n$) [1].

Because asymptotic notations $A(\cdot)$ are fully defined by knowing $A(1)$ the list of necessary arithmetic rules gets shorter. For $A,B,C\in\{o,\omega, \Theta, S\}$ we find:

  1. $(1)_{n\in\mathbb N} \in A(1) \implies (a_n)_{n\in\mathbb N} \in A(a_n)$
  2. $A(1) \subseteq B(1) \implies A(a_n) \subseteq B(a_n)$
  3. $A(1)\cdot B(1) \subseteq C(1) \implies A(a_n)\cdot B(b_n) \subseteq C(a_n\cdot b_n)$
  4. $A(1)\cdot B(1) \subseteq C(1) \implies A(B(a_n)) \subseteq C(a_n)$
  5. $A(1)+ B(1) \subseteq C(1) \implies A(a_n) + B(a_n) \subseteq C(a_n)$

These rules are easy to prove when the property $a_n A(1) = A(a_n)$ is used. For example under the premise $A(1)+ B(1) \subseteq C(1)$ we get

$$A(a_n) + B(a_n) = a_n (A(1)+B(1)) \subseteq a_n C(1) = C(a_n)$$

The arithmetic rules for sets of the form $A(1)$ are often easy to show. For example $O(1)\cdot o(1) \subseteq o(1)$ is the well known proposition

$$\limsup_{n\to\infty} a_n < \infty \land \lim_{n\to\infty} b_n = 0 \implies \lim_{n\to\infty} a_n b_n = 0$$

Thus from rule 4 follow $O(a_n) \cdot o(b_n) \subseteq o(a_n \cdot b_n)$ and from rule 3 follows $O(o(a_n)) \subseteq o(a_n)$.

Conclusion: Many arithmetic rules follow directly for the arithmetic rules for sets of the form $A(1)$ via the relation $a_n A(1) = A(a_n)$. The rules for the sets $A(1)$ are often well known propositions of real analysis for sequences. See also https://math.stackexchange.com/questions/1521135/what-are-the-characteristic-properties-of-asymptotic-notations

$\endgroup$
1
  • $\begingroup$ The idea has some weakness, imho: left side heve meaning when some $a_{n}_{k} = 0$ when right side have not. $\endgroup$
    – zkutch
    Jun 14, 2020 at 22:34
1
$\begingroup$

Taking, for example, non negative case, following definition let us prove most of well known equalities as set equalities : $O(g) = \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n > N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace $

$o(f)=\{g: \exists \epsilon, lim_{n \to \infty}\epsilon=0, \exists N, n>N, g=\epsilon \cdot f \}$

Firstly let me notice, that equality type $f=O(g)$ is quite different from type $O(f)=O(g)$. First means "$\in$", while under second we understand "$\subset \land \supset$".

a) Formal proof example: $O(f) + O(g) = O(f+g) $

  1. "$\subset$".

let's take $ \varphi \in O(f) + O(g)$ then we have $ \exists f_{1} \in O(f)$ and $ \exists g_{1} \in O(g)$ such, that $ \varphi = f_{1} + g_{1} $ and $ \exists C_{1} > 0, \exists N_{1} \in \mathbb{N}, n > N_{1}, \ f_{1}(n) \leqslant C_{1} \cdot f(n) $.
$ \exists C_{2} > 0, \exists N_{2} \in \mathbb{N}, \forall n > N_{2},\ g_{1}(n) \leqslant C_{2} \cdot g(n) $.

So $ \varphi = f_{1} + g_{1} \leqslant C_{1} \cdot f + C_{2} \cdot g \leqslant 2C \cdot (f + g)$, where $ max(C_{1}, C_{2}) = C $ and it holds when $ n>N = max(N_{1}, N_{2}) $. So $ O(f) + O(g) \subset O(f+g)$.

  1. "$\supset$".

Now let's take $ \varphi \in O(f+g) $. Then $ \exists C > 0, \exists N \in \mathbb{N}, n > N $ such, that $ \varphi \leqslant C \cdot (f+g) = C \cdot f+ C \cdot g $. So we can write $ \varphi - C \cdot f \leqslant C \cdot g $. Now let's take representation $ \varphi = C \cdot f + \left( \varphi - C \cdot f\right) $ and notice, that first member of sum is in $ O(f) $ and second in $ O(g) $. So $ O(f+g) \subset O(f) + O(g) $.

b)$O(o(f))=o(f)$

  1. "$\subset$".

Firstly we take $f>0$ and then extend proof. let's take $\varphi \in O(o(f)) \Rightarrow \exists \psi \in o(f), \varphi \leqslant C \cdot \psi \Rightarrow \exists \epsilon, lim_{n \to \infty}\epsilon=0, \space \psi =\epsilon \cdot f \text{ and } \varphi \leqslant C \cdot \epsilon \cdot f$. Now we can set, that $lim_{n \to \infty}\frac{\phi}{f}=0$, so if we consider $\phi=\frac{\phi}{f} \cdot f$, then we obtain $\phi \in o(f)$. And at last lets for case $f \geqslant 0$ consider $N_1 \cap N_2 = \emptyset, N_1 \cup N_2 = \mathbb{N}$ and $0 \in f(N_1)$.

Write, please, which equality proof you would like to see.

$\endgroup$
0
$\begingroup$

The only result needed to prove your first statement is that $\infty > 1 > 0$.

The only result needed to prove the other statements is that, if $\infty > a > 0$ and $\infty > b > 0$, then $\infty > ab > 0$.

$\endgroup$
5
  • $\begingroup$ This doesn't answer the question really $\endgroup$ Nov 8, 2015 at 18:56
  • 1
    $\begingroup$ True, but I think that anyone doing this kind of work should be able to see why they are true. They all follow from the definition of big and little oh. $\endgroup$ Nov 8, 2015 at 19:00
  • 2
    $\begingroup$ Are you sure about the first statment? $f(n)=O(f(n)) \iff \limsup_{n\to\infty} \left|\frac{f(n)}{f(n)}\right| < \infty$ which is true because $\left|\frac{f(n)}{f(n)}\right|=1<\infty$. Do you mean $1 < \infty$ instead of $1 > 0$?! $\endgroup$ Nov 8, 2015 at 19:09
  • $\begingroup$ You are right. I will change it to $0 < 1 < \infty$. $\endgroup$ Nov 8, 2015 at 23:55
  • $\begingroup$ Only for clarification: You say, that the arithmetic rules for asymptotic notations are so intuitive that a proof of them is not necessary? $\endgroup$ Nov 9, 2015 at 13:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .