0
$\begingroup$

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.

Advantages

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?

$\endgroup$

migrated from mathoverflow.net Nov 9 '15 at 14:40

This question came from our site for professional mathematicians.

  • 1
    $\begingroup$ So, your $R_O(a_n)$ means $a_n = O(1)?$ It's common to use $O(1)$ and $o(1)$. $\endgroup$ – Douglas Zare Nov 8 '15 at 23:15
  • $\begingroup$ @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! ;-) $\endgroup$ – Stephan Kulla Nov 8 '15 at 23:24
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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