Sum of Big-O Estimates

Theorem

Sequences

Let $\sequence {a_n},\sequence {b_n},\sequence {c_n},\sequence {d_n}$ be sequences of real or complex numbers.

Let:

$a_n = \map \OO {b_n}$

$c_n = \map \OO {d_n}$

where $\OO$ denotes big-$\OO$ notation.

Then:

$a_n + c_n = \map \OO {\size {b_n} + \size {d_n} }$

Real Analysis

Let $c$ be a real number.

Let $f, g : \hointr c \infty \to \R$ be real functions.

Let $\OO$ denote big-$\OO$ notation.

Let $R_1 : \hointr c \infty \to \R$ be a real function such that $f = \map \OO {R_1}$.

Let $R_2 : \hointr c \infty \to \R$ be a real function such that $g = \map \OO {R_2}$.

Then:

$f + g = \map \OO {\size {R_1} + \size {R_2} }$

Also see

• Product of Big-O Estimates