Subtracting Two same asymptotic values

Question

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?

Answer 1

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

Answer 2

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