0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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)$. $\endgroup$ Jul 26, 2023 at 9:40
  • $\begingroup$ @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 $\endgroup$
    – Zee
    Jul 26, 2023 at 11:13
  • $\begingroup$ 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 $\endgroup$ Jul 26, 2023 at 14:50

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Knowing the constants won't necessarily help. $\endgroup$
    – user16034
    Jul 28, 2023 at 8:45
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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