Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 2 / b

Suppose first that $f=O(g)$. Choose $C>0$ and $N$ so that $|f(n)|\le C|g(n)|$ for $n\ge N$. There are only finitely many natural numbers below $N$. Because $g(n)\ne 0$ at each of them, all ratios $|f(n)|/|g(n)|$ in this finite prefix are finite. LetThen $|f(n)|\le c|g(n)|$ both in the prefix and in the tail, hence on the entire domain of a function. This proves the finite-prefix extension of a big O bound.

Conversely, a bound valid for every natural number is certainly valid eventually. The purported real constant cannot be negative because $g$ never vanishes; if it is zero, enlarge it to a positive constant. The definition of Big O notation then applies. The nonvanishing assumption is what permits the finite exceptions to be absorbed into one constant.