Why sum of two little "o" notation is equal little "o" notation from sum?

2.8k Views Asked by At

Why sum of two little "o" notation is equal little "o" notation from sum?

$o( f(n) ) + o( g(n) ) = o( f(n) + g(n) ) ?$

For example:

  • $f(n) = n^3$
  • $g(n) = 1/n$

so

  • $o(f(n)) = n^2$
  • $o(g(n)) = 1/n^2$

and

  • $o( f(n) ) + o( g(n) ) = n^2 + 1/n^2$
  • $o( f(n) + g(n) ) = n^2$

Of course, I could write it like

  • $o( f(n) ) + o( g(n) ) = n^2 + o( g(n) )$
  • $o( f(n) + g(n) ) = n^2 + o( g(n) )$

My question is why? I don't understand it, because in first we always get two parameters.

1

There are 1 best solutions below

1
On BEST ANSWER

In this notation we always suppose that the function appeared in the parenthesis is positive, for a counter-example of this equality when this assumption is not applied, we can take $1=o(n^2)$ and $0=o(1-n^2)$ which contradicts with $1=o(1)$.

With this observations we have $$ \left|\lim_{n\to \infty} \frac{o(f(n))+o(g(n))}{f(n)+g(n)}\right|\le \left|\lim_{n\to \infty} \frac{o(f(n))}{f(n)}+\lim_{n\to \infty} \frac{o(g(n))}{g(n)}\right|=0 $$ As we want. $\square$