Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 3 / c / Solution

Interpret ${\mathbb{R}}_{+}$ as the strictly positive reals, as in the domain $x>0$ in question 1(e). A bound valid for every $n$ is immediately an eventual bound, by taking $m=0$ (or the least natural number under the other convention).

Conversely, suppose the eventual big O notation bound holds with constants $m,c$. Since $g(j)>0$, all the finitely many ratios $|f(j)|/|g(j)|$ with $j<m$ are finite. Chooseomitting the set of ratios when it is empty. For $n<m$ the definition of $C$ gives $|f(n)|\le C|g(n)|$, and for $n\ge m$ the original bound does so. Hence the two definitions are equivalent for the stated strictly positive codomain.

Strict positivity matters. If ${\mathbb{R}}_{+}$ were instead intended to include zero, an eventual bound need not extend to all indices: $g(0)=0$, $f(0)=1$, and $f(n)=g(n)=1$ for $n\ge 1$ give a counterexample. More generally, extension is possible exactly when each initial zero of $g$ is also a zero of $f$.