Sum of Big-O Estimates/Real Analysis

From ProofWiki
Jump to navigation Jump to search

Theorem

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} }$


Proof

Since:

$f = \map \OO {R_1}$

there exists $x_1 \in \hointr c \infty$ and a real number $C_1$ such that:

$\size {\map f x} \le C_1 \size {\map {R_1} x}$

for $x \ge x_1$.

Similarly, since:

$g = \map \OO {R_2}$

there exists $x_2 \in \hointr c \infty$ and a real number $C_2$ such that:

$\size {\map g x} \le C_2 \size {\map {R_2} x}$

Set:

$x_0 = \max \set {x_1, x_2}$

and:

$C = \max \set {C_1, C_2}$

Then, for $x \ge x_0$ we have:

\(\ds \size {\map f x + \map g x}\) \(\le\) \(\ds \size {\map f x} + \size {\map g x}\) Triangle Inequality
\(\ds \) \(\le\) \(\ds C_1 \size {\map {R_1} x} + C_2 \size {\map {R_2} x}\) since $x \ge x_1$ and $x \ge x_2$
\(\ds \) \(\le\) \(\ds C \size {\map {R_1} x} + C \size {\map {R_2} x}\)
\(\ds \) \(=\) \(\ds C \size {\size {\map {R_1} x} + \size {\map {R_2} x} }\)

That is, by the definition of big-$\OO$ notation, we have:

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

$\blacksquare$