Substitution in Big-O Estimate/Sequences
Jump to navigation
Jump to search
Theorem
Let $(a_n)$ and $(b_n)$ be sequences of real or complex numbers.
Let $a_n = O(b_n)$ where $O$ denotes big-O notation.
Let $(n_k)$ be a diverging sequence of natural numbers.
Then $a_{n_k} = O(b_{n_k})$.
Proof
Because $a_n = O(b_n)$, there exists $M\geq0$ and $n_0 \in\N$ such that $|a_n| \leq M \cdot |b_n|$ for $n\geq n_0$.
Because $n_k$ diverges, there exists $k_0\in\N$ such that $n_k\geq n_0$ for $k\geq k_0$.
Then $|a_{n_k}| \leq M\cdot |b_{n_k}|$ for $k\geq k_0$.
Thus $a_{n_k} = O(b_{n_k})$.
$\blacksquare$