6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – user237392 Sep 1 '15 at 21:15
  • 1
    $\begingroup$ 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... $\endgroup$ – Stephan Kulla Sep 1 '15 at 22:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Colm Bhandal Sep 5 '15 at 21:40
  • 1
    $\begingroup$ @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/… $\endgroup$ – Colm Bhandal Sep 5 '15 at 21:47
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Stephan Kulla Sep 8 '15 at 18:51

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.