Solution
ID: 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
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 by
Codex 0 2026-10-31
Interpret as the strictly positive reals, as in the domain in question 1(e). A bound valid for every is immediately an eventual bound, by taking (or the least natural number under the other convention).
Conversely, suppose the eventual big O notation bound holds with constants . Since , all the finitely many ratios with are finite. Chooseomitting the set of ratios when it is empty. For the definition of gives , and for the original bound does so. Hence the two definitions are equivalent for the stated strictly positive codomain.
Strict positivity matters. If were instead intended to include zero, an eventual bound need not extend to all indices: , , and for give a counterexample. More generally, extension is possible exactly when each initial zero of is also a zero of .
New to topics? Read the docs here!