> [!NOTE] Theorem (Necessary Condition for Big-O) > Let $f,g:\mathbb{N}\to{\mathbb{R}}$ be [[Real sequences|real sequences]]. If the sequence $\frac{g(n)}{f(n)}$ is [[Convergence|convergent]] (or equivalently, $\lim_{ n \to \infty } \frac{f(n)}{g(n)}\neq 0$) then $g$ is [[Big O Relation on Real Sequences|big O]] of $f$ and conversely, if the $g(n)=\mathcal{O}(f(n))$ then $\frac{g(n)}{f(n)}$ is [[Bounded Sequence|bounded]] for all $n\geq N$ for some $N\in \mathbb{N}$. **Proof**: By [[Reciprocal of Terms of Properly Divergent Real Sequence Tends to Zero]], $\lim_{ n \to \infty } \frac{f(n)}{g(n)}\neq 0$ iff $\lim_{ n \to \infty } \frac{g(n)}{f(n)}\neq \infty.$ Suppose $g(n)=\mathcal{O}(f(n)).$ Then, there exists $c>0,$ $N\in \mathbb{N}$ such that for all $n \geq N,$ $|g(n)|\leq c \cdot |f(n)|$ $\left\lvert \frac{g(n)}{f(n)} \right \rvert \leq c$thus $\frac{g(n)}{f(n)}$ is bounded. Suppose there exists $l\in \mathbb{R}$ so that $\lim_{ n \to \infty } \frac{g(n)}{f(n)}=l.$ Then, by definition, for all $\varepsilon>0,$ there exists $N\in N$ so that for all $n \geq N,$ $\left\lvert \frac{g(n)}{f(n)} - l \right\rvert <\varepsilon $which gives $\left\lvert \frac{g(n)}{f(n)} \right\rvert < l+\varepsilon \implies |g(n)|< (l+\varepsilon)|f(n)|$thus $g(n)= \mathcal{O}(f(n)).$