-1

How does the sustraction works for big O notation?

I have to functions, lets say $f(x)=p(x)+O(\ln(r(x)))$ and $g(x)=q(x)+O(\ln(s(x)))$ and I want to consider $f(x)-g(x)$ there is a way to simplify $O(\ln(r(x)))-O(\ln(s(x)))$? What this even means?

Thanks.

Edit: The explicit case I am looking for is

\begin{eqnarray} f(x)&=&(n-(x-1)d)\log(n-(x-1)d)+O(\log(n-(x-1)d))\\ g(x)&=&x\log(x)+O(\log(x)) \\ h(x)&=&(n-1-(x-1)(d+1))\log(n-1-(x-1)(d+1))+O(\log(n-1-(x-1)(d+1))) \end{eqnarray}

This 3 expresions cames to apply some algebra and Stirling approximation to $\log\binom{n-(q-1)d}{q}$ and that's why I need to consider $f(x)-g(x)-h(x)$

Luis GC
  • 412
  • Unless you have some reason to believe that there is some cancellation all you can say is that this grows no faster than $p$. Subtracting the big-O expressions makes no sense. If you provide an explicit example where you want to bound the growth rate of the difference we may be able to help. – Ethan Bolker Apr 11 '18 at 14:29
  • Oh, ok, I will edit to add the explicit case. – Luis GC Apr 11 '18 at 14:37
  • $O(\ln(r(x))$ would not normally tell us anything because $r(x)$ could be huge – Ross Millikan Apr 11 '18 at 14:44
  • Are $n,d$ fixed? Then $f(x) \in O(1)$ because $f(x) \lt n \ln n$ which is a constant. $g(x)$ is the only one that grows with $x$ – Ross Millikan Apr 11 '18 at 15:03
  • @RossMillikan $d$ is fixed, $n$ is going to infinity linear with $x$ – Luis GC Apr 12 '18 at 07:43
  • Please include all the necessary information in your question. There are occurrences of $n-dx$ in many places. Does that grow, shrink, or stay the same? It is only after this comment that came to light. – Ross Millikan Apr 12 '18 at 13:56

1 Answers1

2

Generally, if $f(x)$ and $g(x)$ are in the same big O class, you know their sum and difference are in the same class. The sum or difference may be in a smaller class. For example, if $f(x)=x^3, g(x)=x^3-x$ we have $f(x) \in O(x^3), g(x) \in O(x^3)$, which tells us that $f(x)-g(x) \in O(x^3)$ as well. In fact, $f(x)-g(x)=x \in O(x)$ but we need to find the cancellation to know that.

Ross Millikan
  • 374,822