Transitivity of Big-O Estimates/Sequences

Theorem

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

Let $a_n = \map \OO {\sequence {b_n} }$ and $b_n = \map \OO {\sequence {c_n} }$, where $\OO$ denotes big-$\OO$ notation.

Then $a_n = \map \OO {\sequence {c_n} }$.

Proof

Because $a_n = \map \OO {\sequence {b_n} }$, there exists $K \ge 0$ and $n_0 \in \N$ such that $\size {a_n} \le K \cdot \size {b_n}$ for $n \ge n_0$.

Because $b_n = \map \OO {\sequence {c_n} }$, there exists $L \ge 0$ and $n_1 \in \N$ such that $\size {b_n} \le L \cdot \size {c_n}$ for $n \ge n_1$.

Then $\size {a_n} \le K L \cdot \size {c_n}$ for $n \ge \max \set {n_0, n_1}$.

Thus $a_n = \map \OO {\sequence {c_n} }$.

$\blacksquare$