Big O notation sum rule

proof-writing asymptotics

Given $T_1(n)=O(f(n))$ and $T_2(n)=O(g(n))$, we are to prove $$T_1(n)+T_2(n)=O(\max(f(n),g(n))\tag0$$

  • Write down exactly what the first assumption says: there exists a constant $C_1$ and an index $N_1$ such that $$|T_1(n)| \le C_1f(n)\quad \text{when } n\ge N_1 \tag1$$

  • Write down exactly what the second assumption says: there exists a constant $C_2$ and an index $N_2$ such that $$|T_2(n)| \le C_2g(n)\quad \text{when } n\ge N_2 \tag2$$

  • Prepare to combine (1) and (2) by introducing $N=\max(N_1,N_2)$ and $C=\max(C_1,C_2)$.

  • Add (1) and (2): $$ |T_1(n)|+|T_2(n)|\le C_1f(n)+C_2g(n) \le C(f(n)+g(n))\quad \text{when } n\ge N \tag3 $$

  • Check that for any two real numbers $a,b$ we have $$a+b\le 2\max(a,b)\tag4$$

  • Use (4) in (3) to obtain $$ |T_1(n)|+|T_2(n)|\le 2C\max(f(n),g(n))\quad \text{when } n\ge N \tag5 $$

  • Conclude that (0) holds.

Related

Hard inequality $ (xy+yz+zx)\left(\frac{1}{(x+y)^2}+\frac{1}{(y+z)^2}+\frac{1}{(z+x)^2}\right)\ge\frac{9}{4} $
Frobenius norm is not induced
Distribution of weighted sum of Bernoulli RVs
For symmetric stable distributions, why is $\alpha \le 2$?
In polar coordinates, can r be negative?
Riemann Zeta Function's Analytic Continuation
Does $\mathbb R^2$ contain more numbers than $\mathbb R^1$? [duplicate]
What application is there for a non-Hausdorff topological space?
Help to show that $\bigoplus_{i\in\mathbb{N}}\mathbb{Z}\cong\operatorname{Hom}(\prod_{i\in\mathbb{N}}\mathbb{Z},\mathbb{Z})$.
How to prove $ \int_0^\infty e^{-x^2} \; dx = \frac{\sqrt{\pi}}2$ without changing into polar coordinates?
Non-measurable set in product $\sigma$-algebra s.t. every section is measurable.
A proof for $\nabla |u|^p = p\ \text{sgn}(u)|u|^{p-1}\nabla u$.