# Generalization of asymptotic notations like big O or little o notation

## Context and question

For a thesis I need to prove all the arithmetic rules for asymptotic notations – such as $O(\cdot)$ or $\omega(\cdot)$ – I have used (which are a lot). Currently I look for a list of already proved rules which I may cite. While thinking about the arithmetic rules I found a possible generalization for these asymptotic notations which make showing the arithmetic rules easier. My question will be

Question: Is this kind of generalization already known or used? Is this generalization useful and how would you improve it?

I describe my idea in the following. I am sorry for the long post and I want to thank you in advance for reading it. I hope MO is the right place for it because it describes a new idea. Please feel free to migrate this question to MSE when it fits there better than here.

## My idea for the generalization

Take $O(\cdot)$ which is defined via (I assume here and in the following that $(a_n)$ is a strictly positive sequence):

$$(\epsilon_n)_{n\in\mathbb N} \in O(a_n) \iff \limsup_{n\to\infty} \left|\frac {\epsilon_n}{a_n}\right| < \infty$$

When we define the statement form $R_O\Big( (b_n)_{n\in\mathbb N} \Big) \iff \limsup_{n\to\infty} b_n < \infty$ we can write $$(\epsilon_n) \in O(a_n)_{n\in\mathbb N} \iff R_O\left(\left|\frac {\epsilon_n}{a_n}\right|\right)$$

Similary we find statement forms like $R_o$, $R_\omega$ or $R_\Omega$ for other asymptotic notations (I use the notation $(\epsilon_n)_{n\in\mathbb N} \in S(a_n)$ instead of $\epsilon_n \sim a_n$):

\begin{align} (\epsilon_n)_{n\in\mathbb N} \in o(a_n) \iff R_o\left(\left|\frac {\epsilon_n}{a_n}\right|\right) \text{ with }R_o\Big( (b_n)_{n\in\mathbb N} \Big) \iff \lim_{n\to\infty} b_n = 0 \\ (\epsilon_n)_{n\in\mathbb N} \in \omega(a_n) \iff R_\omega\left(\left|\frac {\epsilon_n}{a_n}\right|\right) \text{ with }R_\omega\Big( (b_n)_{n\in\mathbb N} \Big) \iff \lim_{n\to\infty} b_n = \infty \\ (\epsilon_n)_{n\in\mathbb N} \in \Omega(a_n)\iff R_\Omega\left(\left|\frac {\epsilon_n}{a_n}\right|\right) \text{ with }R_\Omega\Big( (b_n)_{n\in\mathbb N} \Big) \iff \liminf_{n\to\infty} b_n > 0 \\ (\epsilon_n)_{n\in\mathbb N} \in S(a_n) \iff R_S\left(\left|\frac {\epsilon_n}{a_n}\right|\right) \text{ with }R_S\Big( (b_n)_{n\in\mathbb N} \Big) \iff \lim_{n\to\infty} b_n = 1 \end{align}

So each asymptotic notation can be defined by a statement form for sequences which gives a common property of all asymptotic notations.

By defining new statement forms $R_A\Big( (b_n)_{n\in\mathbb N} \Big)$ one can define new asymptotic notations $A(a_n)$. For example from $R_\Psi\Big( (b_n)_{n\in\mathbb N} \Big) \iff \limsup_{n\to\infty} b_n \le 1$ we get the "Big Psi notation" and from $R_\Delta\Big( (b_n)_{n\in\mathbb N} \Big) \iff \sup_{n\in\mathbb N} b_n \le 1$ we get the "Big Delta notation".

Also proving all the possible arithmetic rules become easier. For $A, B, C \in \{O, o, \omega, \Theta, S\}$ we have:

1. $R_A\Big( (1)_{n\in\mathbb N} \Big) \implies (a_n) \in A(a_n)$
2. From $R_A\Big( (a_n)_{n\in\mathbb N} \Big) \implies R_B\Big( (a_n)_{n\in\mathbb N} \Big)$ follows the rule $A(a_n) \subseteq B(a_n)$.
3. From $R_A\Big( (a_n)_{n\in\mathbb N} \Big) \land R_B\Big( (b_n)_{n\in\mathbb N} \Big) \implies R_C\Big( (a_n\cdot b_n)_{n\in\mathbb N} \Big)$ follows the rules $A(B(a_n)) \subseteq C(a_n)$ and $A(a_n) \cdot B(b_n) \subseteq C(a_n\cdot b_n)$
4. From $R_A\Big( (a_n)_{n\in\mathbb N} \Big) \land R_B\Big( (b_n)_{n\in\mathbb N} \Big) \implies R_C\Big( (a_n + b_n)_{n\in\mathbb N} \Big)$ follows the rule $A(a_n) + B(a_n) \subseteq C(a_n)$

For example the arithmetic rule $O(o(a_n)) \subseteq o(a_n)$ can be derived by rule 3 from 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 \cdot b_n =0$$

So from proving the above rules 1-4 (which is easy) we get a lot of arithmetic rules for asymptotic notations. ;-) Now my question is:

Question: Is this kind of generalization already known or used? Is this generalization useful and how would you improve it?

## migrated from mathoverflow.netNov 9 '15 at 14:40

This question came from our site for professional mathematicians.

• So, your $R_O(a_n)$ means $a_n = O(1)?$ It's common to use $O(1)$ and $o(1)$. – Douglas Zare Nov 8 '15 at 23:15
• @DouglasZare: Oh Yeah, that's right! (and so trivial.. why didn't I see it?!) Thanks for pointing me to this fact. That helps me a lot! ;-) – Stephan Kulla Nov 8 '15 at 23:24

As Douglas Zare pointed out in his comment, the proposed generalization is unnecessary. The relation $$(\epsilon_n) \in O(a_n)_{n\in\mathbb N} \iff R_O\left(\left|\frac {\epsilon_n}{a_n}\right|\right)$$ can be rewritten as $$(\epsilon_n) \in O(a_n)_{n\in\mathbb N} \iff \left(\left|\frac {\epsilon_n}{a_n}\right|\right)_{n\in\mathbb N} \in O(1)$$ This can be even condensed to the equation $O(a_n)=a_n \cdot O(1)$. So the concept with the statement $R_O$ is not necessary. However it shows that $O(a_n)$ is fully determined by $O(1)$ via the relation $O(a_n)=a_n \cdot O(1)$. Also the proposed rules can be rewritten. For example the rule
• From $R_A\Big( (a_n)_{n\in\mathbb N} \Big) \land R_B\Big( (b_n)_{n\in\mathbb N} \Big) \implies R_C\Big( (a_n + b_n)_{n\in\mathbb N} \Big)$ follows the rule $A(a_n) + B(a_n) \subseteq C(a_n)$
becomes $$A(1)+ B(1) \subseteq C(1) \implies A(a_n) + B(a_n) \subseteq C(a_n)$$ I gave more details about this in my answer to the question Arithmetic rules for big O notation, little o notation and so on... I also made a follow up question: https://math.stackexchange.com/questions/1521135/what-are-the-characteristic-properties-of-asymptotic-notations