# Name for kind of big O notation with leading coefficient

Context: As known the big O notation $O(f(n))$ describes a function $g(n)$ such that there is a constant $C \ge 0$ with $\limsup_{n\to\infty} \left|\frac{g(n)}{f(n)}\right| \le C$ (I assume that $f(n)$ is never zero). Thus the big O notation can be used to characterize the speed of convergence (for example for an algorithm). So I can write $$a(n) = a + O\left(\frac 1n\right)$$ which means that the function / algorithm $a(n)$ calculates in almost all calculation steps $n$ the desired number $a$ with an error less than $\frac Cn$ for a constant $C\ge 0$.

Problem: Whereby I can compare two algorithms by their speed of convergence with the big O notation, the above notation $a(n) = a + O\left(\frac 1n\right)$ does not say anything about the actual error in the n-th step because I do not know the constant $C\ge 0$.

My solution: One may introduce a new notation, lets say the big Psi notation $\Psi(f(n))$ which is defined as

$$g(n)\in \Psi(f(n)) \iff \limsup_{n\to\infty} \left|\frac{g(n)}{f(n)}\right| < 1$$

For example one may write $$a(n) = a + \Psi\left(\frac{42}{n}\right)$$ so that $a(n)\in O\left(\frac 1n\right)$ with the constant $C=42$. There are also arithmetic rules for the big Psi notation similar to the rules for the big notation, for example:

$$\left(1+\Psi\left(\frac an\right)\right)\left(1+\Psi\left(\frac bn\right)\right)\subseteq 1+\Psi\left(\frac{a+b+ab}{n}\right)$$

My question: Because the proposed solution is simple and somehow straightforward I guess there was already a mathematician who wrote about it. Can you point me to a textbook/paper where this notation is discussed, please? How is this notation called in mathematics?

So far I have only found the big Omega notation and the big Theta notation...

Update: After rethinking the notation I would now define

$$g(n)\in \Psi(f(n)) \iff \limsup_{n\to\infty} \left|\frac{g(n)}{f(n)}\right| \le 1$$

such that

$$\left(1+\Psi\left(\frac an\right)\right)\left(1+\Psi\left(\frac bn\right)\right)\subseteq 1+\Psi\left(\frac{a+b}{n}\right)$$

because

$$\limsup_{n\to\infty} \frac{\frac{a+b}{n}}{\frac{a+b}{n}+\frac{ab}{n^2}} = 1$$

• So your "problem" is that you want to communicate the bounding constant? If you knew that (say C=42), wouldn't you simply be able to say $T_a(n) \leq a+ \frac{42}{n}$ (i.e., directly bound the running time? The $O$ notations are asymptotic notions anyway, it doesn't imply that it holds for finite $n$. – user237392 Sep 1 '15 at 21:15
• I want to use this notation for proofs to calculate the bounding constant after (a long) calculation (or better to say: the asymptotic bounding constant). See this proof of Moivre-Laplace theorem, where the big O notation is used in a way I want to use the above proposed notation. I know that I can define this notation easily by myself, but I want to know whether something like this already exists... – Stephan Kulla Sep 1 '15 at 22:27
• @tampis I wondered before why the bounding constant was "swallowed" in the big O notation. I guess the answer is that it's generally "uninteresting" for most usages. However, it seems what you've defined there is perfectly valid: you only swallow up the additive constant in your definition. So you're still less accurate than an exact bound/value for the function, but not as fuzzy as the big O. Unfortunately no references for you, but I'd also be surprised if it hasn't been written about before. – Colm Bhandal Sep 5 '15 at 21:40
• @tampis, again, just to follow up from my previous comment, here is a discussion I found among the programmers as to why the constant is generally ignored: programmers.stackexchange.com/questions/171701/… – Colm Bhandal Sep 5 '15 at 21:47

If I had to give your expression a name, "asymptotically less than" seems reasonable among the possibilities that are still relatively succinct.

I have seen the notation $f(n) \lesssim g(n)$ used to mean something similar to what you're trying to write for $f(n) = \Psi(g(n))$ (except that the lim sup is $\le 1$ rather than $< 1$), but it doesn't seem to be very well-known (for instance, this MSE thread suggests that it's not very standardized, and it even completely misses the interpretation I'm referring to). There does exist a $\lnsim$ symbol as well that perhaps might express the $<1$ that you want in your notation, but I'm really not sure how well that reads.

I do recognize the usefulness of having both functional and relational notations for the same concept (just as $O(\cdot)$ and $\ll$ each have their own uses), and I have myself defined ad hoc notation for this purpose. I don't think there is anything standard for this, so it seems reasonable to define your own. But I think it would read more naturally if you tied it to the $O$ notation more closely (since it really is $O$ with greater specificity). Some suggestions would be $\hat{O}$ or $O^{<1}$, or maybe $\tilde{O}$ but I've seen that last one used to mean something quite different ($O$ allowing a multiplicative error of some power of $\log n$).

I don't think that your $\Psi$ notation has any advantage over $a(n) \le a+\frac1{n}$. It does not really hide anything, which the "O" and "o" notations excel at.

Also, your equation $$\left(1+\Psi\left(\frac an\right)\right)\left(1+\Psi\left(\frac bn\right)\right)\subseteq 1+\Psi\left(\frac{a+b+ab}{n}\right)$$ is not correct, or at least more imprecise than needed, because

$(1+\frac{a}{n})(1+\frac{b}{n}) =1+\frac{a+b}{n}+\frac{ab}{n^2}$. The problem is in the $ab$ term. If it goes over $n$, then the term is larger than necessary, and if it is put over $n^2$, that term will get swallowed by $\frac{a+b+\epsilon}{n}$ for any $\epsilon > 0$.

• Yeah, I would now redefine the notation such that $\left(1+\Psi\left(\frac an\right)\right)\left(1+\Psi\left(\frac bn\right)\right)\subseteq 1+\Psi\left(\frac{a+b}{n}\right)$ for $a,b\in\mathbb R$ (see my update to the question). Thanks for your answer! – Stephan Kulla Sep 8 '15 at 18:51