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?
Best Answer
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.