# Subtracting Two same asymptotic values

I am dealing with two values $$a$$ and $$b$$ such that they grow at the same asymptotic rate, i.e., $$O(\frac{1}{\sqrt{N}})$$. I want to achieve a reasonable bound for the difference $$a - b$$. When I go into the fundamentals in terms of $$c_1, c_2$$, I run into multiple issues. The difference be $$(c_1 - c_2)\frac{1}{\sqrt{N}}$$. Here we can cases for which this function becomes negative, thus defining it as $$O(1)$$. Or if it is positive, then it will be $$O(\frac{1}{\sqrt{N}})$$.

I know that when dealing with differences, asymptotic bounds of the form $$O$$ do not work very well since they talk about $$\exists c$$. I want to get some insights on how to proceed, am I recommended to switch to a different form of bound, perhaps $$o$$ bound?

• If you only know that $|a| \le \frac{c_1}{\sqrt{N}}$ and $|b| \le \frac{c_2}{\sqrt{N}}$, the best you can say in general is $a - b = O\left(\frac{1}{\sqrt{N}}\right)$. Jul 26 at 9:40
• @Gribouillis may you please refer me to any form of bounds that would be useful in coming up with a better bound for their difference Jul 26 at 11:13
• As @Gribouillis says, given only the information you have provided, the best thing you can say in general is $a-b \in O\left(\frac{1}{\sqrt{N}}\right)$. But if you know/have access to more specifics you might be able to say more. This might be helpful: stackoverflow.com/a/1364582 Jul 26 at 14:50

I make an example: if $$a=\frac{2}{\sqrt{n}}$$ and $$b=\frac{1}{\sqrt{n}}$$, then both are $$O(\frac{1}{\sqrt{n}})$$ and $$a-b=\frac{1}{\sqrt{n}}=O(\frac{1}{\sqrt{n}})= \Theta (\frac{1}{\sqrt{n}})$$. If instead $$a=b=\frac{1}{\sqrt{n}}$$, then we have $$a-b=0=O(1)$$.

As you can see, without further information on $$a$$ and $$b$$, the only thing we can say is that $$a-b=O(\frac{1}{\sqrt{n}})$$.

The fact is that, without further information about $$a$$ and $$b$$, you can't know the constants $$c_1$$ and $$c_2$$ (nor the lower order terms).

Why do you want to subtract terms in big-O notation? Is this operation well-defined? Think about it

• Knowing the constants won't necessarily help.
– user16034
Jul 28 at 8:45

If $$a(n),b(n)=O(g(n))$$ then without more information, all you can say is $$a(n)-b(n)=O(g(n))$$, even if the asymptotic constants are the same and are tight.

Even worse, if $$a(n),b(n)=\Theta(g(n))$$ then without more information, all you can say is $$a(n)-b(n)=O(g(n))$$, even if the respective tightest upper and lower asymptotic constants are the same!

Example: $$H_n$$ ($$n^{\text{th}}$$ harmonic number), $$\lg(n)$$ (base $$2$$ logarithm) and $$\log(n)+\gamma$$ (Mascheroni's constant) are all three $$\Theta(\log(n))$$.

Then $$H_n-\lg(n)=\Theta(\log(n))$$, $$H_n-\log(n)=\Theta(1)$$, and $$H_n-(\log(n)+\gamma)=\Theta(n^{-2})$$. All these differences are $$O(\log(n))$$.