# Arithmetic rules for big O notation, little o notation and so on...

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.

• 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. Nov 8, 2015 at 18:41
• 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.
– zhw.
Nov 8, 2015 at 18:41
• @Omnomnomnom: Oh, thanks a lot! ;-) Nov 8, 2015 at 18:58
• @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 ;-) Nov 8, 2015 at 18:59

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.

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

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

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

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.

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

• This doesn't answer the question really Nov 8, 2015 at 18:56
• 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. Nov 8, 2015 at 19:00
• 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$?! Nov 8, 2015 at 19:09
• You are right. I will change it to $0 < 1 < \infty$. Nov 8, 2015 at 23:55
• Only for clarification: You say, that the arithmetic rules for asymptotic notations are so intuitive that a proof of them is not necessary? Nov 9, 2015 at 13:39