Sum of Big O - which one is it?

asymptotics

On the wikipedia page, we have the following property:

If $f_1(x) = O(g_1(x))$ and $f_2(x) = O(g_2(x))$ then $f_1(x) + f_2(x) = O(|g_1(x)| + |g_2(x)|)$.

But in my textbook, I also see the following sum property:

If $f_1(x) = O(g_1(x))$ and $f_2(x) = O(g_2(x))$ then $f_1(x) + f_2(x) = O(\max(g_1(x), g_2(x)))$.

Are these two properties equivalent? If not, which sum property do I use in general?


Solution 1:

They are equivalent (assuming that $g_1,g_2$ are assumed non-negative in your textbook). Note that $$ \max(a,b)\leq a+b \leq 2\max(a,b) $$ for any $a,b\geq 0$, and that the constant $2$ can be "hidden" in the $O(\cdot)$ notation.

Related

Cohomology ring of $H^*(A_5;\mathbb Z_2)$?
Unsure of my work evaluating $\int \frac{dx}{\sqrt{x + \sqrt{x + \sqrt{x + \cdots}}}}$
Prove that $\int_0^1 \big(1-x^2\big) \big(f'(x)\big)^2\,dx \ge 24 \left(\int_0^1 xf(x)\,dx\right)^{\!2}$
Why are $\Delta_1$ sentences of arithmetic called recursive?
What should the high school math curriculum consist of?
Is there a connection between length of sentence and length of proof?
What is average distance from center of square to some point?
How do I convert the distance between two lat/long points into feet/meters?
What do the $p$-adic roots of unity look like?
Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$
prove that $\lim\limits_{x\to 1}\frac{x^{1/m}-1}{x^{1/n}-1}=\frac{n}{m}$
Good books/expository papers in moduli theory